§ 10.3. И снова Ферма

Наибольшее известное составное число Ферма — это число его делитель равен Число чудовищно велико, и у Вас, естественно, возникает вопрос: каким замечательным алгоритмом удается найти его делитель? Ответить на него легко. Это метод Эйлера, описанный в предыдущем параграфе. Однако вместо того, чтобы слепо следовать Эйлеру, мы перевернем метод с ног на голову. Эйлер начинал с конкретного числа Ферма и пытался найти его

делитель. Мы же возьмем число, которое может быть делителем какого-то и будем искать соответствующее

Алгоритм начинается с выбора двух натуральных чисел: к и первое из которых должно быть нечетным. Затем строится число Как следует из метода Эйлера, оно делит число Ферма тогда и только тогда, когда

Для работы с большими числами, подобными упомянутому выше, нам потребуется очень эффективный способ вычисления сравнений. Поскольку мы имеем дело только со степенями двойки, найти такой способ довольно просто, так как

Теперь поступаем следующим образом. Для начала положим Переменная используется для хранения информации о показателе. Мы стартуем с потому что простое при Суть алгоритма состоит в замене на вычет числа по модулю и увеличении на 1 в каждом цикле. Останавливается алгоритм в одном из двух случаев: либо либо В первом из них делит а во втором не является делителем ни одного из Напомним, что если делит число то

Этот метод с некоторыми изящными усовершенствованиями был использован Гостином (Gostin) при определении делителей чисел (см. [19]). Он написал программу на языках и ассемблере, распараллелив некоторые процедуры. На первом этапе программа генерирует несколько миллионов возможных значений чисел Затем из них удаляются все, делящиеся на небольшие простые числа. Выжившие проверяются сравнениями, как объяснялось выше.

На следующей странице пирведена часть таблицы из работы [19]. Она содержит те значения натуральных для которых к является множителем числа

(см. скан)