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

Ро-алгоритм ($\rho$-алгоритм) — предложенный в 1975году алгоритм, служащий для факторизации (разложения на множители) целыхчисел. Данный алгоритм основывается на алгоритме Флойда поиска длиныцикла в последовательности и некоторых следствиях из парадокса днейрождений. Алгоритм наиболее эффективен при факторизации составных чиселс достаточно малыми множителями в разложении. Сложность алгоритмаоценивается как $O(N^{1/4})$.
 ρ-алгоритм Полларда строит числовую последовательность, элементы которойобразуют цикл, начиная с некоторого номера n, что может бытьпроиллюстрировано, расположением чисел в виде греческой буквы ρ, чтопослужило названием семейству алгоритмов.

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


 В конце 60-х годов XX века Роберт Флойд придумал достаточно эффективныйрешения задачи нахождения цикла, также известный, как алгоритм «черепахаи заяц». Джон Поллард, Дональд Кнут и другие математики проанализировалиповедение этого алгоритма в среднем случае. Было предложено несколькомодификаций и улучшений алгоритма.
 В 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 десятичных цифр.
 В рамках проекта «» алгоритм Полларда помог найти делитель длиной 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$ раз. Если при этом число не было до концафакторизовано, выбирается, например, другое начальное число $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
  3. Если $d>1$, то вычисление заканчивается, и найденное на предыдущем шаге число $d$ является делителем $N$. Если $N/d$ не является простым числом, то процедуру поиска делителей продолжается, взяв в качестве $N$ число $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, \ldots, а $i$принимает значения из интервала $[2^{k}+1; 2^{k+1}]$. Например, $k=3$,$j=2^3=8$, а $i\in [9;16]$.
 Эта идея была предложена Ричардом Брентом в 1980 году и позволяетуменьшить количество выполняемых операций приблизительно на 25 Ещё одна вариация ρ-алгоритма Полларда была разработана Флойдом.Согласно Флойду, значение $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:
 n = 8051,   F(x) = (x\textsuperscript2 +3) mod n ,   x\textsubscript0 =y\textsubscript0 = 2
i
1
2
3
4

 Таким образом, d\textsubscript1 = 97,d\textsubscript2 = 83 — нетривиальные делители числа8051.
 После нахождения делителя числа, в ρ-алгоритме предлагается продолжатьвычисления и искать делители числа $N/d$, если $N/d$ не являетсяпростым. В этом простом примере данного шага совершать не потребовалось.

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


 Алгоритм основывается на известном парадоксе дней рождения.
 Следует отметить, что вероятность $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.4 q} \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}$, тос вероятностью, превышающей $1/2$ , делитель $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)^2$, не превосходит величины$e^{-\lambda}$. Данное утверждение следует из парадокса дней рождения.

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


 Объём памяти, используемый алгоритмом, можно значительно уменьшить.
 \texttt \textttint\texttt \textttRho-Поллард\texttt (\textttint\texttt N)\\\texttt \{ \\\texttt   \textttint\texttt x = \textttrandom\texttt(1, N-2);\\\texttt   \textttint\texttt y = 1; \textttint\texttt i = 0; \textttint\texttt stage = 2;\\\texttt   \textttwhile\texttt (Н.О.Д.(N, \textttabs\texttt(x - y)) == 1)\\\texttt   \{\\\texttt     \textttif\texttt (i == stage)\{\\\texttt       y = x;\\\texttt       stage = stage*2; \\\texttt     \}\\\texttt     x = (x*x - 1) (mod N);\\\texttt     i = i + 1;\\\texttt   \}\\\texttt   \textttreturn\texttt \textttН.О.Д\texttt(N, \textttabs\texttt(x-y));\\\texttt \}
 В этом варианте вычисление требует хранить в памяти всего три переменные$N$, $x$, и $y$, что выгодно отличает алгоритм в такой реализации отдругих методов факторизации чисел.

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


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

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

agraphСистема с общейпамятью
 Предыдущий метод, очевидно, можно использовать и на системах с общейпамятью, однако, гораздо разумнее использовать единый генератор $F(x)$.