Жак Арсак - Программирование игр и головоломок

Идея в том, чтобы образовать произведение на некоторое число этих разностей по модулю n , а затем брать н. о. д. этих разностей и n . Если одна из этих разностей имеет с n н. о. д., отличный от 1, то для произведения будет выполняться то же самое. Выбор числа членов для участия в произведении предоставляется вашему усмотрению. Если членов слишком мало, то вы вычисляете много н о. д. и замедляете метод. Если членов много, то вы делаете ненужные операции! вы долго ждете перед тем, как обнаружить делитель…

2. Если эта первая программа уже готова, переходите к гораздо большим числам. Нужно выполнить следующие операции:

произведение двух чисел по модулю n ,

н. о. д. двух чисел, числа n и числа, меньшего n .

Настоящая трудность — это произведение по модулю n . Так как к ней часто обращаются, то она должна быть оптимальной…

Может оказаться опасным пускаться в этот метод Полларда, не зная, является ли исследуемое число составным. Используйте для этого тест Ферма.

В этом единственную трудность представляет возведение x в степень n − 1 по модулю n .

Следовательно, пусть нужно вычислить y = x p .

Примем следующую индуктивную гипотезу: искомый результат имеет вид y = u kw .

Если k есть нуль, то u k = 1 и потому у = w , и все закончено.

Если k не нуль и если k четно, то u k = u 2( k /2)= ( u 2) k /2.

Заменяя u на u * u и k на k /2 возвращаемся к общей ситуации.

Если k нечетно, то u k = u * u 2(( k −1)/2)

w * u k = ( w * u ) * ( u 2) ( k −1)/2

Заменим w на w * u , u на u * u и k на целую часть от k /2.

Все это должно проделываться по модулю n . Операции над k не содержат трудностей. Если числа достаточно малы, то вы действуете обычными умножениями или делениями.

Если же числа не являются достаточно малыми, то все сводится к предыдущему случаю. Но у вас здесь есть элемент ответа. Я уже говорил вам, как можно вычислить y = x p с помощью бинарного разложения p , выполняя умножения только по модулю n . Переделайте то же рассуждение для y = p * x , заменяя возведение в степень умножением, а умножение — сложением. Предположите, что результат имеет вид

y = k * u + w .

Если k четно, то k * u ( k /2) * ( u + u ), и т. д.

Сложения нужно делать по модулю n , что не требует, впрочем, операции деления…

Я на своем компьютере получил отличные результаты для теста Ферма. А метод Полларда-Брента еще остается очень медленным. Работайте надежно. Можно ли пользоваться программой, в правильности которой вы не уверены?

Головоломка 17.

Подсказка: эта программа сообщает, делится ли n на b .

Головоломка 18.

Снова подсказка: эта программа выводит НЕТ, если n не является точным квадратом; в противном случае она выводит квадратный корень из n . Но это из области бесполезных подсказок. Как вы сможете показать, что эта программа действительно делает то, что я анонсировал? Испытав ее? Вы можете испытать все целые?

По индукции? Почему бы и нет? Напишите мне, если получится…

Головоломка 19.

Не пренебрегайте крохами информации, которые можно извлечь из текста программы. Вполне правдоподобна гипотеза, что eps — параметр, характеризующий точность, маленький и потому вещественный. Следовательно, p и q , и — вследствие этого — a и b имеют хорошие шансы оказаться вещественными. Примите это как гипотезу, касающуюся типа данных и результата.

Вы не можете исследовать плоскость a , b , чтобы увидеть, что же именно вычисляет эта программа. Но можно сделать несколько простых замечаний. Пусть f ( a , b ) — значение, вычисляемое программой.

Вы без особых усилий сумеете показать, что

f ( a , b ) = f( b , a ),

f ( ac , bc ) = cf ( a , b )

и вследствие этого

f ( a , b ) = bf ( a / b , 1).

Ho g ( x ) = f ( x , 1) — функция только одного аргумента. Можно ограничиться областью x ≥ 1. Я написал программу, вычисляющую g (простой и очевидный вариант предыдущей программы), а затем вычислил g для

x = 1, 2, 3, …, 10,

x = 1.1, 1.2, 1.3, …, 1.9.

Природа функции g становится очевидной, если исходить из этой таблицы. Уразумев, что именно нужно доказать, мы справимся с этим без труда.