Наконец, господин S получает решение. Следовательно, среди всех пар с суммой s есть только одна пара, дающая произведение с упомянутым выше свойством.
Компьютер нужен, чтобы порождать списки и вычеркивать в них. В конце должна оставаться одна и только одна пара.
Головоломка 16.
Я предлагаю вам решить эту задачу в два приема.
1. Составьте сначала программу по методу Полларда-Брента о «маленькими» числами, иначе говоря, такими, что машина представляет их бее округления или усечения, Это зависит от машины. Я на своей машине могу получить около 8·106, что немного. Возникают еще некоторые сомнения, как только принимаются во внимание деления…
Чтобы узнать, становится ли последовательность периодической, вы можете ограничиться рассмотрением разностей ai − aj, где i и j меняются в соответствии с вполне определенными законами, Вам следует рассматривать н. о. д. этих разностей и n. Это невыполнимо для каждой разности и потребует много времени.
Идея в том, чтобы образовать произведение на некоторое число этих разностей по модулю n, а затем брать н. о. д. этих разностей и n. Если одна из этих разностей имеет с n н. о. д., отличный от 1, то для произведения будет выполняться то же самое. Выбор числа членов для участия в произведении предоставляется вашему усмотрению. Если членов слишком мало, то вы вычисляете много н о. д. и замедляете метод. Если членов много, то вы делаете ненужные операции! вы долго ждете перед тем, как обнаружить делитель…
2. Если эта первая программа уже готова, переходите к гораздо большим числам. Нужно выполнить следующие операции:
произведение двух чисел по модулю n,
н. о. д. двух чисел, числа n и числа, меньшего n.
Настоящая трудность — это произведение по модулю n. Так как к ней часто обращаются, то она должна быть оптимальной…
Может оказаться опасным пускаться в этот метод Полларда, не зная, является ли исследуемое число составным. Используйте для этого тест Ферма.
В этом единственную трудность представляет возведение x в степень n − 1 по модулю n.
Следовательно, пусть нужно вычислить y = xp.
Примем следующую индуктивную гипотезу: искомый результат имеет вид y = ukw.
Если k есть нуль, то uk = 1 и потому у = w, и все закончено.
Если k не нуль и если k четно, то uk = u2(k/2) = (u2)k/2.
Заменяя u на u * u и k на k/2 возвращаемся к общей ситуации.
Если k нечетно, то uk = u * u2((k−1)/2)
w * uk = (w * u) * (u2)(k−1)/2
Заменим w на w * u, u на u * u и k на целую часть от k/2.
Все это должно проделываться по модулю n. Операции над k не содержат трудностей. Если числа достаточно малы, то вы действуете обычными умножениями или делениями.
Если же числа не являются достаточно малыми, то все сводится к предыдущему случаю. Но у вас здесь есть элемент ответа. Я уже говорил вам, как можно вычислить y = xp с помощью бинарного разложения p, выполняя умножения только по модулю n. Переделайте то же рассуждение для y = p * x, заменяя возведение в степень умножением, а умножение — сложением. Предположите, что результат имеет вид
y = k * u + w.
Если k четно, то k * u (k/2) * (u + u), и т. д.
Сложения нужно делать по модулю n, что не требует, впрочем, операции деления…
Я на своем компьютере получил отличные результаты для теста Ферма. А метод Полларда-Брента еще остается очень медленным. Работайте надежно. Можно ли пользоваться программой, в правильности которой вы не уверены?
Головоломка 17.
Подсказка: эта программа сообщает, делится ли n на b.
Головоломка 18.
Снова подсказка: эта программа выводит НЕТ, если n не является точным квадратом; в противном случае она выводит квадратный корень из n. Но это из области бесполезных подсказок. Как вы сможете показать, что эта программа действительно делает то, что я анонсировал? Испытав ее? Вы можете испытать все целые?