Участник:Pyatakovns/Ро-алгоритм Полларда

Автор: Пятаков Н.С. 419 группа

Свойства и структура алгоритмов

Общее описание алгоритма

Ро-алгоритм Полларда предназначен для решения задачи факторизации целых чисел. Этот метод был разработан Джоном Поллардом в 1975 г. Данный алгоритм основывается на следствиях из парадокса дней рождения и алгоритме Флойда поиска длины цикла в последовательности. Алгоритм наиболее эффективен при факторизации составных чисел с достаточно малыми множителями в разложении. Сложность алгоритма оценивается как [math]\displaystyle{ O(N^{1/4}) }[/math].

Ро-алгоритм Полларда строит числовую последовательность, элементы которой образуют цикл, начиная с некоторого номера n, что может быть проиллюстрировано, расположением чисел в виде греческой буквы [math]\displaystyle{ ρ }[/math], что послужило названием семейству алгоритмов.

Математическое описание алгоритма

Пусть n – число, которое следует разложить. ρ-метод Полларда работает следующим образом:

1. Выбираем произвольное небольшое число [math]\displaystyle{ x_0 }[/math] и строим последовательность чисел [math]\displaystyle{ {x_n}, n = 0, 1, 2, ..., }[/math] определяя каждое следующее [math]\displaystyle{ x_{n+1} }[/math] по формуле [math]\displaystyle{ x_{n+1} =(x_{n}^2 −1)(modn) }[/math].

2. Одновременно на каждом шаге [math]\displaystyle{ i }[/math] вычисляем [math]\displaystyle{ Н.О.Д. }[/math] [math]\displaystyle{ d }[/math] числа [math]\displaystyle{ n }[/math] и всевозможных разностей [math]\displaystyle{ |x_i − x_j| }[/math], где [math]\displaystyle{ j \lt i }[/math].

3. Когда будет найден [math]\displaystyle{ d }[/math] [math]\displaystyle{ = }[/math] [math]\displaystyle{ Н.О.Д.(n, |x_i−x_j|) }[/math], отличный от [math]\displaystyle{ 1 }[/math], вычисление заканчивается. Найденное [math]\displaystyle{ d }[/math] является делителем [math]\displaystyle{ n }[/math]. Если [math]\displaystyle{ n/d }[/math] не является простым числом, то процедуру можно продолжить, взяв вместо [math]\displaystyle{ n }[/math] число [math]\displaystyle{ n/d }[/math].

Вместо функции [math]\displaystyle{ F (x) = (x^2 − 1) (mod n) }[/math] в вычислении [math]\displaystyle{ x_n+1 }[/math] можно взять другой многочлен, например, [math]\displaystyle{ x^2 + 1 }[/math] или произвольный многочлен степени большей или равной двум.

Недостатком данного варианта метода является необходимость хранить большое число предыдущих значений [math]\displaystyle{ x_j }[/math] . Если [math]\displaystyle{ (x_j −x_i)≡0(modp) }[/math], то[math]\displaystyle{ (f(x_j)−f(x_i))≡0(modp) }[/math], поэтому, если пара [math]\displaystyle{ (x_i, x_j) }[/math] дает нам решение, то решение даст любая пара [math]\displaystyle{ (x_{i+k}, x_{j+k}) }[/math].

Поэтому, нет необходимости проверять все пары [math]\displaystyle{ (x_i, x_j) }[/math], а можно ограничиться парами виды [math]\displaystyle{ (x_i, x_j) }[/math], где [math]\displaystyle{ j = 2k }[/math] , и [math]\displaystyle{ k }[/math] пробегает набор последовательных значений [math]\displaystyle{ 1, 2, 3,..., }[/math] а [math]\displaystyle{ i }[/math] принимает значения из интервала [math]\displaystyle{ [2^k + 1; 2^{k+1}] }[/math].