Ρ-алгоритм Полларда

ρ-aлгоритм Джона Полларда, предложенный им в 1975 году, служит для факторизации целых чисел. Он основан на том, что число n имеет такой простой делитель p, для которого p-1 является произведением небольших простых чисел.

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

Неформальное описание алгоритма Полларда 1975:

• Предположим, что число n имеет такой простой делитель p, для которого $p-1$ является произведением небольших простых чисел.
• Согласно малой теореме Ферма, если число p не делит число a , то $a^{p-1}=1(mod p)$

Следовательно, p является делителем числа $(a^{p-1}-1,n)$

• Разумеется, вначале мы не знаем числа p и поэтому не можем реально вычислить $a^{p-1}-1$.

Вместо этого, возьмём целое число k, которое представляет из себя произведение нескольких первых простых чисел в небольших положительных степенях.

• Вычислим теперь D=НОД$(a^k-1,n)$.

Заметим, что для этого необходимо найти $(a^k-1)$ только по модулю n. Поэтому из сказанного выше следует, что для вычисления D=НОД$(a^k-1,n)$ требуется $2log_2 (2kn)$ операций. Такое вычисление может быть проделано в разумное время, даже если k и n имеют по тысяче знаков.

• Если число n имеет простой делитель p, для которого (p-1)|k, то p будет делителем числа $(a^k-1)$. Поэтому, в этом случае мы имеем

$(a^k-1,n)>=p>=1$

Если $(a^k-1)$≠n, то мы получаем нетривиальный делитель числа n. По-этому мы можем разложить n на два множителя и применить к каждому из них описанную процедуру. Если же,$(a^k-1)=n$ то выбираем новое a. Если же $(a^k-1)=1$ выбираем новый показатель k, больший предыдущего.

Формальное описание алгоритма Полларда выглядит следующим образом:

• Пусть N составное целое положительное число.
• Шаг 1. Выбираем число k, являющееся произведением небольших простых чисел в небольших степенях. Например,k=НОК{${2,3..M}$} для некоторого целого положительного числа M.
• Шаг 2. Выбираем произвольное число a, удовлетворяющее условию $1<a<n$
• Шаг 3. Вычисляем наибольший общий делитель $(a,n)$ . Если НОД$(a,n)>1$, то мы получаем нетривиальный множитель n. Если (a,n)=1 переходим к следующему шагу.
• Шаг 4. Вычисляем $D=(a^k-1,n)$.

Если $1<D<n$, то D является делителем числа N . Если $D=1$, то возвращаемся к шагу 1 и выбираем больший показатель k . Если $D=n$ возвращаемся к шагу 2 и выбираем новое число a .

Литература

• 1. О.Н. Василенко. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2003.
• 2. Ю.П. Соловьев, В.А. Садовничий, Е.Т. Шавгулидзе, В.В. Белокуров. Эллиптические кривые и современные алгоритмы теории чисел. Москва – Ижевск: Институт компьютерных исследований, 2003.

Сложность алгоритма

Пусть $n$ — составное число. Тогда существует такая константа $C$, что для любого положительного числа $\lambda$ вероятность события, состоящего в том, что ρ-метод Полларда не найдет нетривиального делителя $n$ за время $C\sqrt{\lambda \sqrt n}(\log n)^3$, не превосходит величины $e^{-\lambda}$.