§ 3.4. Алгоритм Ферма разложения на множители

Алгоритм из § 3.2 эффективен только в случае, если у числа разложение которого мы ищем, есть маленький простой делитель. Насколько этот делитель должен быть мал, зависит от компьютера. В настоящем параграфе мы изучаем алгоритм, который эффективен, когда есть делитель (не обязательно простой), незначительно превосходящий Идею алгоритма

придумал Ферма, и она требует гораздо большей изобретательности, чем алгоритм деления методом проб.

Предположим для начала, что нечетное. Если бы оно было четным, то 2 было бы его делителем. Ключевая идея алгоритма состоит в том, чтобы попробовать представить в виде где неотрицательные целые числа. Если такие числа найдены, то

Значит, у являются делителями числа

Чтобы отвлечься от посторонних деталей, будем предполагать, что компьютер умеет вычислять целую часть числа

Проще всего применять алгоритм Ферма к полным квадратам. Если для некоторого целого числа то является делителем Тогда . С другой стороны, если то

Алгоритм Ферма разложения на множители Ввод: нечетное натуральное число

Вывод: множитель числа или сообщение о том, что простое.

Шаг 1. Положить Если то х является делителем числа и работа алгоритма останавливается; в противном случае увеличить на 1 и перейти к шагу 2. Шаг 2. Если то число простое, и работа алгоритма останавливается; в противном случае вычислить

Шаг 3. Если число у целое (т. е., если ), то раскладывается в произведение и работа алгоритма останавливается; в противном случае увеличить на 1 и перейти к шагу 2.

Как показывает следующий пример, этот алгоритм очень прост в применении. Допустим, мы хотим разложить на множители число Сначала переменной х присваивается целая часть числа . В примере она равна Однако

Поэтому мы должны увеличить на 1. Мы продолжим этот процесс до тех пор, пока число не станет целым или не будет выполняться равенство Заметим, что в нашем примере Значения переменных х и у после завершения каждого цикла приведены в таблице.

(см. скан)

Таким образом, на шестом цикле мы получили целое число. Значит, искомые числа Соответствующие множители равны