Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 53 стр.

Глава 2. Простые алгоритмы факторизации                                54

В наихудшем случае, когда q близко к 1, а p близко к n, алгоритм будет
работать даже хуже, чем метод пробных делений. Действительно, A = (p +
q)/2, откуда число итераций в методе Ферма равно
                                   p+q            n
                     Iter(n) =         − bn1/2 c ≈ − bn1/2 c,
                                    2             2
т.е. имеет порядок 0(n). Для того, чтобы метод Ферма работал не хуже, чем
метод пробных делений необходимо, чтобы Iter(n) было меньше n1/2 , откуда
больший делитель p < 4n1/2 .
      Таким образом, как и метод пробного деления, алгоритм Ферма имеет
экспоненциальную оценку и не эффективен для разложения длинных чисел.
      Можно улучшить метод Ферма, выполнив сначала пробное деление
числа n на числа от 2 до некоторой константы B , исключив тем самым
малые делители n до B включительно, и только потом выполнить поиск
методом Ферма.


2.2. (p − 1)–метод Полларда
       Этот метод был разработан английским математиком Джоном
Поллардом в 1974 г. и опубликован в [43].
      Пусть n—факторизуемое число, а 1 < p < n– его простой делитель.
Согласно малой теореме Ферма, для любого a, 1 ≤ a < p, выполняется
условие ap−1 ≡ 1( mod p).
      Это же сравнение выполнится, если вместо степени p − 1 взять
произвольное натуральное число M кратное p−1, т.к. если M = (p−1)·k , то
aM = (ap−1 )k ≡ 1k ≡ 1( mod p). Последнее условие эквивалентно aM − 1 = pr
для некоторого целого r . Отсюда, если p является делителем числа n, тогда
p является делителем наибольшего общего делителя Н.О.Д.(n, aM − 1) и
совпадет с Н.О.Д.(n, aM − 1), если aM − 1 < n. Пусть
                                            t
            p − 1 = pri 1 · pr22 · ... · prt .                      (2.22)

      Идея (p − 1)–метод Полларда состоит в чтобы выбрать M в виде
произведения как можно большего числа простых сомножителей или их