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

Числовая последовательность зацикливается, начиная с некотрого n. Цикл может быть представлен в виде греческой буквы ρ.

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

Во всех ρ-методах Полларда строится числовая последовательность, элементы которой образуют цикл, начиная с некоторого номера n, что может быть проиллюстрировано, расположением чисел в виде греческой буквы ρ. Это и послужило названием семейству методов.

История алгоритма

В конце 60х годов 20 века Роберт Флойд придумал дочтаточно эффективный алгоритм поиска длины цикла в последовательности, также известный, как алгоритм "черепаха и заяц". Джон Поллард, Дональд Кнут и другие математики проанализировали поведение этого алгоритма в среднем случае. Было предложено несколько модификаций и улучшений алгоритма.

В 1975 году Поллард опубликовал статью, в которой он, основываясь на алгоритме Флойда обнаружения циклов, изложил идею алгоритма факторизации чисел, работающего за время, пропорциональное $N^{1/4}$. Автор алгоритма назвал его методом факторизации Монте-Карло, отражая кажущуюся случайность чисел, генерируемых в процессе вычисления. Однако позже метод все-таки получил свое современное название — ρ-aлгоритм Полларда.

В 1981 году Ричард Брент и Джон Поллард с помощью алгоритма нашли наименьшие делители чисел Ферма $F_{n}=2^{2^{n}}+1$ при $5\leq n\leq 13$. Так, $F_{8}=1238926361552897\cdot p_{62}$, где $p_{62}$ - простое число, состоящее из 62 десятичных цифр.

В рамках проекта "Cunningham project" алгоритм Полларда помог найти делитель длиной 19 цифр числа $2^{2386}+1$. Большие делители также могли бы быть найдены, однако открытие метода факторизации с помощью эллиптических кривых сделало алгоритм Полларда неконкурентоспособным.

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

Неформальное описание

Рассмотрим последовательность целых чисел ${x_{n}}$, такую что $x_{0}=2$ и $x_{i+1}=x_{i}^{2}-1\,(\mathrm {mod} \,n)$, где $n$ - число, которое нужно факторизовать. Оригинальный алгоритм выглядит следующим образом.

1. Будем вычислять тройки чисел

$(x_{i},x_{2i},Q_{i}),i=1,2,...$, где $Q_{i}\equiv \prod _{j=1}^{i}(x_{2j}-x_{j})\,(\mathrm {mod} \,n)$.

Причем каждая такая тройка получается из предыдущей.

2. Каждый раз, когда число $i$ кратно числу $m$ (скажем, $m=100$), будем вычислять наибольший общий делитель $d_{i}=\mathrm {GCD} (Q_{i},n)$ любым известным методом.

3. Если $1<d_{i}<n$, то найдено частичное разложения числа $n$, причем $n=d_{i}\times (n/d_{i})$.

Найденный делитель $d_{i}$ может быть составным, поэтому его также необходимо факторизовать. Если число $n/d_{i}$ составное, то продолжаем алгоритм с модулем $n'=n/d_{i}$.

4. Вычисления повторяются $S$ раз. Например, можно пректратить алгоритм при $i=S=10^{5}$. Если при этом число не было до конца факторизовано, можно выбрать, например, другое начальное число $x_{0}$.

Формальное описание

Пусть $n$ составное целое положительное число, которое требуется разложить на множители. Алгоритм выглядит следующим образом:

1. Выбираем небольшое число $x_{0}$ и строим последовательность $\{x_{n}\},n=0,1,2,...$, определяя каждое следующее как $x_{n+1}=F(x_{n})\,(\mathrm {mod} \,\,n)$.
2. Одновременно на каждом i-ом шаге вычисляем $d=\mathrm {GCD} (n,|x_{i}-x_{j}|)$ для каких-либо $i$, $j$ таких, что $j<i$.
3. Если обнаружили, что $d>1$, то вычисление заканчивается, и найденное на предыдущем шаге число $d$ является делителем числа $n$. Если $n/d$ не является простым числом, то процедуру можно продолжить, взяв в качестве $n$ число $n/d$.

Как на практике выбирать функцию $F(x)$? Функция должна быть не слишком сложной для вычисления, но в то же время не должна быть линейным многочленом, а также не должна порождать взаимно однозначное отображение. Обычно в качестве $F(x)$ берут функцию $F(x)=x^{2}\pm 1(\mathrm {mod} \,n)$ или $F(x)=x^{2}\pm a(\mathrm {mod} \,n)$. Однако, не следует использовать функции $x^{2}-2$ и $x^{2}$.

Если известно, что для делителя $p$ числа $n$ справедливо $p\equiv 1\,(\mathrm {mod} \,k)$ при некотором $k>2$, то имеет смысл использовать $F(x)=x^{k}+b$.

Существенным недостатком алгоритма в такой реализации является необходимость хранить большое число предыдущих значений $x_{j}$.

Улучшения алгоритма

Изначальная версия алгоритма обладает рядом недостатков. В настоящий момент существует несколько подходов к улучшению оригинального метода.

Пусть в оригинальном алгоритме $F(x)=(x^{2}-1)\mathrm {mod} \,n$. Заметим, что если $(x_{j}-x_{i})\equiv 0(\mathrm {mod} \,p)$, то $(f(x_{j})-f(x_{i}))\equiv 0(\mathrm {mod} \,p)$, поэтому, если пара $(x_{i},x_{j})$ дает нам решение, то решение даст любая пара $(x_{i+k},x_{j+k})$.

Поэтому, нет необходимости проверять все пары $(x_{i},x_{j})$, а можно ограничиться парами вида $(x_{i},x_{j})$, где $j=2^{k}$, и $k$ пробегает набор последовательны значений 1, 2, 3, ..., а $i$ принимает значения из интервала $[2^{k}+1;2^{k+1}]$. Например, $k=3$, $j=2^{3}=8$, а $i\in [9;16]$. Эта идея была предложена Ричардом Брентом в 1980 году и позволяет уменьшить количество выполняемых операций приблизительно на 25%.

Еще одна вариация P-метода полларда была разработана Флойдом. Согласно Флойду, значение y обновляется на каждом шаге по формуле $y=F^{2}(y)=F(F(y))$, поэтому на шаге i будут получены значения $x_{i}=F^{i}(x_{0})$, $y_{i}=x_{2i}=F^{2i}(x_{0})$, и НОД на этом шаге вычисляется для $n$ и $y-x$.

Пример факторизации числа

Пусть $n=8051$, $F(x)=(x^{2}+1)\,\mathrm {mod} \,8051$, $x_{0}=2$.

i	xi	yi	НОД(|xi − yi|, 8051)
1	5	26	1
2	26	7474	1
3	677	871	97

Таким образом, 97 - нетривиальный делитель числа 8051. Используя другие варианты полинома $F(x)$, можно также получить делитель 83.

Обоснование P-метода Полларда

Алгоритм основывается на известном парадоксе дней рождения.

Теорема. (Парадокс дней рождения)

Пусть $\lambda >0$. Для случайной выборки из $l+1$ элементов, каждый их которых меньше $q$, где $l={\sqrt {2\lambda q}}$, вероятность того, что два элемента окажутся одинаковыми $p>1-\exp ^{-\lambda }$.

Следует отметить, что вероятность $p=0.5$ в парадоксе дней рождения достигается при $\lambda \approx 0.69$.

Пусть последовательность $\{u_{n}\}$ состоит из разностей $x_{i}-x_{j}$, проверяемых в ходе работы алгоритма. Определим новую последовательность $\{z_{n}\}$, где $z_{n}=u_{n}\,\mathrm {mod} \,q$, $q$ — меньший из делителей числа $n$.

Все члены последовательности $\{z_{n}\}$ меньше ${\sqrt {n}}$. Если рассматривать её как случайную последовательность целых чисел, меньших $q$, то, согласно парадоксу дней рождения, вероятность того, что среди $l+1$ её членов попадутся два одинаковых, превысит $1/2$ при $\lambda \approx 0.69$, тогда $l$ должно быть не меньше ${\sqrt {2\lambda q}}\approx {\sqrt {1.4q}}\approx 1.18{\sqrt {q}}$.

Если $z_{i}=z_{j}$, тогда $x_{i}-x_{j}\equiv 0\,\mathrm {mod} \,q$, то есть, $x_{i}-x_{j}=kq$ для некоторого целого $k$. Если $x_{i}\neq x_{j}$, что выполняется с большой вероятностью, то искомый делитель $q$ числа $n$ будет найден как $\mathrm {GCD} (n,|x_{i}-x_{j}|)$. Поскольку ${\sqrt {q}}\leq n_{1/4}$, то с вероятностью, превышающей 0.5, делитель $n$ будет найден за $1.18\times n^{1/4}$ итераций.

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

Чтобы оценить сложность алгоритма, можно рассматривать последовательность, строящуюся в процессе вычислений, как случайную (разумеется, ни о какой строгости при этом говорить нельзя). Чтобы полностью факторизовать число $n$ длиной $\beta$ бит, достаточно найти все его делители, не превосходящие ${\sqrt {n}}$, что требует максимум порядка ${\sqrt {n}}$ арифметических операций, или $n^{1/4}\beta ^{2}=2^{\beta /4}\beta ^{2}$ битовых операций.

Поэтому сложность алгоритма оценивается, как $O(n^{1/4})$. Однако в этой оценке не учитываются накладные расходы по вычислению наибольшего общего делителя. Полученная сложность алгоритма, хотя и не является точной, достаточно хорошо согласуется с практикой.

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

Особенности реализации

Объем памяти, используемый алгоритмом, можно значительно уменьшить.

 int Rho-Поллард (int n)
 { 
   int x = random(1, n-2);
   int y = 1; int i = 0; int stage = 2;
   while (Н.О.Д.(n, abs(x  y)) == 1)
   {
     if (i == stage ){
       y = x;
       stage = stage*2; 
     }
     x = (x*x + 1) (mod n);
     i = i + 1;
   }
   return Н.О.Д(n, abs(x-y));
 }

В этом варианте вычисление требует хранить в памяти всего три переменные $n$, $x$, и $y$, что выгодно отличает метод в такой реализации от других методов факторизации чисел.

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

Алгоритм Полларда допускает распараллеливание с импользованием любого стандарта параллельных вычислений (например, OpenMP и др.).

Существует несколько вариантов распараллеливания, но их общая идея заключается в том, что каждый процессор исполняет последовательный алгоритм, причем исходное число $x_{0}$ и/или полином $F(x)$ должны быть различными для каждого процессора. Однако такая параллельная реализация не дает линейного ускорения.

Предположим что есть $P$ одинаковых процессоров. Если мы используем $P$ различных последовательностей (т.е. различных полиномов $F(x)$), то вероятность того, что первые $k$ чисел в этих последовательностях будут различными по модулю $p$ будет примерно равна $\exp({-k^{2}P}/{2p})$. Таким образом, ускорение можно оценить как $P^{1/2}$.

Ричард Крандалл предположил, что достижимо ускорение $O(P/(log{P})^{2})$, однако данное утверждение пока не проверено.

Литература

• Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: Учебное пособие. — Казань: Казанский Университет, 2011. — С. 61-64. — 190 с.
• О.Н. Василенко. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2003.
• Ю.П. Соловьев, В.А. Садовничий, Е.Т. Шавгулидзе, В.В. Белокуров. Эллиптические кривые и современные алгоритмы теории чисел. Москва – Ижевск: Институт компьютерных исследований, 2003.
• Brent, Richard P. (1980), "An Improved Monte Carlo Factorization Algorithm" (PDF), BIT, 20: 176—184, doi:10.1007/BF01933190
• Childs, Lindsay N. Congruences // Введение в высшую алгебру = Concrete Introduction to Higher Algebra. — 3-е изд. — USA: Springer, 2009. — С. 471-473. — 603 с. — ISBN 978-0-387-74725-5.
• Koshy T. Congruences // Элементарная теория чисел и ее приложения = Elementary Number Theory with Applications. — 2-е изд. — USA: Academic Press, 2007. — С. 238. — 771 с. — ISBN 9780123724878.
• Pollard J. M. Методы факторизации и проверка простоты. (англ.) = Theorems on factorization and primality testing. // Математические Труды Кэмбриджского Философского Общества (Mathematical Proceedings of the Cambridge Philosophical Society). — 1974. — Т. 76, № 3. — С. 521. — doi:10.1017/S0305004100049252.
• Reisel, H. Простые числа и компьютерные методы факторизации = Prime Numbers and Computer Methods for Factorization. — 2-е изд. — USA: Springer, 2012. — С. 183. — 464 с. — ISBN 978-0-8176-8297-2.

См. также

• P-1 алгоритм Полларда
• P+1 алгоритм Уильямса
• Метод пробных делений
• Метод Ферма
• P-метод Полларда дискретного логарифмирования