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

Эта статья — об алгоритме факторизации чисел. О методе дискретного логарифмирования см. ро-метод Полларда для дискретного логарифмирования.

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

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

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

История алгоритмаПравить

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

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

В 1981 году Ричард Брент и Джон Поллард с помощью алгоритма нашли наименьшие делители чисел Ферма $F_n=2^{2^n}+1$$F_{n}=2^{2^{n}}+1$  при $5\le <!--\; \le \; -->n\le <!--\; \le \; -->13$$5\leq n\leq 13$ . Скорость алгоритма сильно зависит лишь от величины наименьшего делителя исходного числа, но не от самого числа. Так, поиск наименьшего делителя седьмого числа Ферма — $\begin{array}{l}{F}_7=340282366920938463463374607431768211457=59649589127497217\cdot <!--\; \cdot \; -->5704689200685129054721;\end{array}$${\begin{array}{lll}F_{7}=340282366920938463463374607431768211457=59\,649\,589\,127\,497\,217\cdot 5\,704\,689\,200\,685\,129\,054\,721;\end{array}}$ , занимает гораздо больше времени, чем поиск делителя двенадцатого числа Ферма (т.к. его делитель 114689 значительно меньше, хотя само число состоит более чем из 1200 десятичных цифр).

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

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

Оригинальная версияПравить

Рассматривается последовательность целых чисел $x_n$${x_{n}}$ , такая что $x_0=2$$x_{0}=2$  и $x_{i+1}=(x_i^2-<!--\; -\; -->1)(\mathrm{m}\mathrm{o}\mathrm{d}N)$$x_{i+1}=(x_{i}^{2}-1\,)(\mathrm {mod} \,N)$ , где $N$$N$  — число, которое нужно факторизовать. Оригинальный алгоритм выглядит следующим образом:

1. Вычисляются тройки чисел

$(x_i,x_{2i},Q_i),i=1,2,...$$(x_{i},x_{2i},Q_{i}),i=1,2,...$ , где $Q_i\equiv <!--\; \equiv \; -->\underset{j=1}{\overset{i}{\prod <!--\; \prod \; -->}}(x_{2j}-<!--\; -\; -->x_j)(\mathrm{m}\mathrm{o}\mathrm{d}N)$$Q_{i}\equiv \prod _{j=1}^{i}(x_{2j}-x_{j})\,(\mathrm {mod} \,N)$ .

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

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

3. Если $1<d_{i}<N$ , то частичное разложение числа $N$$N$  найдено, причём $N=d_i\times <!--\; \times \; -->(N/d_i)$$N=d_{i}\times (N/d_{i})$ .

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

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

Современная версияПравить

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

1. Случайным образом выбирается небольшое число $x_0$$x_{{0}}$  и строится последовательность $\{x_n\},n=0,1,2,...$$\{x_{n}\},n=0,1,2,...$ , определяя каждое следующее как $x_{n+1}=F(x_n)(\mathrm{m}\mathrm{o}\mathrm{d}N)$$x_{n+1}=F(x_{n})\,(\mathrm {mod} \,\,N)$ .
2. Одновременно на каждом i-ом шаге вычисляется $d=\mathrm{G}\mathrm{C}\mathrm{D}(N,|x_i-<!--\; -\; -->x_j|)$$d=\mathrm {GCD} (N,|x_{i}-x_{j}|)$  для каких-либо $i$$i$ , $j$$j$  таких, что $j<i$ , например, $i=2j$$i=2j$ .
3. Если $d>1$$d>1$ , то вычисление заканчивается, и найденное на предыдущем шаге число $d$$d$  является делителем $N$$N$ . Если $N/d$$N/d$  не является простым числом, то процедуру поиска делителей продолжается, взяв в качестве $N$$N$  число $N^{\prime }=N/d$$N'=N/d$ .

На практике функция $F(x)$$F(x)$  выбирается не слишком сложной для вычисления (но в то же время не линейным многочленом), при условии того, что она не должна порождать взаимно однозначное отображение. Обычно в качестве $F(x)$$F(x)$  выбираются функции $F(x)=x^2\pm <!--\; \pm \; -->1(\mathrm{m}\mathrm{o}\mathrm{d}N)$$F(x)=x^{2}\pm 1(\mathrm {mod} \,N)$  или $F(x)=x^2\pm <!--\; \pm \; -->a(\mathrm{m}\mathrm{o}\mathrm{d}N)$$F(x)=x^{2}\pm a(\mathrm {mod} \,N)$ . Однако функции $x^2-<!--\; -\; -->2$$x^{2}-2$  и $x^2$$x^{2}$  не подходят.

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

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

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

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

Пусть $F(x)=(x^2-<!--\; -\; -->1)modN$$F(x)=(x^{2}-1){\bmod {N}}$ . Тогда, если $(x_j-<!--\; -\; -->x_i)\equiv <!--\; \equiv \; -->0(\mathrm{mod}p)$$(x_{j}-x_{i})\equiv 0{\pmod {p}}$ , то $(F(x_j)-<!--\; -\; -->F(x_i))\equiv <!--\; \equiv \; -->0(\mathrm{mod}p)$$(F(x_{j})-F(x_{i}))\equiv 0{\pmod {p}}$ , поэтому, если пара $(x_i,x_j)$$(x_{i},x_{j})$  даёт решение, то решение даст любая пара $(x_{i+k},x_{j+k})$$(x_{i+k},x_{j+k})$ .

Поэтому нет необходимости проверять все пары $(x_i,x_j)$$(x_{i},x_{j})$ , а можно ограничиться парами вида $(x_i,x_j)$$(x_{i},x_{j})$ , где $j=2^k$$j=2^{k}$ , и $k$$k$  пробегает набор последовательных значений 1, 2, 3, …, а $i$$i$  принимает значения из интервала $[2^k+1;2^{k+1}]$$[2^{k}+1;2^{k+1}]$ . Например, $k=3$$k=3$ , $j=2^3=8$$j=2^{3}=8$ , а $i\in <!--\; \in \; -->[9;16]$$i\in [9;16]$ .

Эта идея была предложена Ричардом Брентом в 1980 году и позволяет уменьшить количество выполняемых операций приблизительно на 25 %.

Ещё одна вариация ρ-алгоритма Полларда была разработана Флойдом. Согласно Флойду, значение $y$$y$  обновляется на каждом шаге по формуле $y=F^2(y)=F(F(y))$$y=F^{2}(y)=F(F(y))$ , поэтому на шаге $i$$i$  будут получены значения $x_i=F^i(x_0)$$x_{i}=F^{i}(x_{0})$ , $y_i=x_{2i}=F^{2i}(x_0)$$y_{i}=x_{2i}=F^{2i}(x_{0})$ , и НОД на этом шаге вычисляется для $N$$N$  и $y-<!--\; -\; -->x$$y-x$ .

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

Данный пример наглядно демонстрирует ρ-алгоритм факторизации (версия алгоритма, с улучшением Флойда), для числа N = 8051:

Таблица: факторизация числа 8051

n = 8051, F(x) = (x2 + 1) mod n , x0 = y0 = 2
i	xi=F(xi-1)	yi=F(F(yi-1))	НОД(|xi − yi|, 8051)
1	5	26	1
2	26	7474	1
3	677	871	97

Используя другие варианты полинома $F(x)$$F(x)$ , можно также получить делитель 83:

Таблица: факторизация числа 8051

n = 8051, F(x) = (x2 + 3) mod n , x0 = y0 = 2
i	xi=F(xi-1)	yi=F(F(yi-1))	НОД(|xi − yi|, 8051)
1	7	52	1
2	52	1442	1
3	2707	778	1
4	1442	3932	83

Таким образом, d₁ = 97, d₂ = 83 — нетривиальные делители числа 8051.

После нахождения делителя числа, в ρ-алгоритме предлагается продолжать вычисления и искать делители числа $N/d$$N/d$ , если $N/d$$N/d$  не является простым. В этом простом примере данного шага совершать не потребовалось.

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

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

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

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

Пусть последовательность $\{u_n\}$$\{u_{n}\}$  состоит из разностей $x_i-<!--\; -\; -->x_j$$x_{i}-x_{j}$ , проверяемых в ходе работы алгоритма. Определяется новая последовательность $\{z_n\}$$\{z_{n}\}$ , где $z_n=u_n\mathrm{m}\mathrm{o}\mathrm{d}q$$z_{n}=u_{n}\,\mathrm {mod} \,q$ , $q$$q$  — меньший из делителей числа $N$$N$ .

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

Если $z_i=z_j$$z_{i}=z_{j}$ , тогда $x_i-<!--\; -\; -->x_j\equiv <!--\; \equiv \; -->0\mathrm{m}\mathrm{o}\mathrm{d}q$$x_{i}-x_{j}\equiv 0\,\mathrm {mod} \,q$ , то есть, $x_i-<!--\; -\; -->x_j=kq$$x_{i}-x_{j}=kq$  для некоторого целого $k$$k$ . Если $x_i\ne <!--\; \ne \; -->x_j$$x_{i}\neq x_{j}$ , что выполняется с большой вероятностью, то искомый делитель $q$$q$  числа $N$$N$  будет найден как $\mathrm{G}\mathrm{C}\mathrm{D}(N,|x_i-<!--\; -\; -->x_j|)$$\mathrm {GCD} (N,|x_{i}-x_{j}|)$ . Поскольку $\sqrt{q}\le <!--\; \le \; -->n^{1/4}$${\sqrt {q}}\leq n^{1/4}$ , то с вероятностью, превышающей $1/2$$1/2$  , делитель $N$$N$  будет найден за $1.18\times <!--\; \times \; -->N^{1/4}$$1.18\times N^{1/4}$  итераций.

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

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

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

Справедливо следующее утверждение: пусть $N$$N$  — составное число. Тогда существует такая константа $C$$C$ , что для любого положительного числа $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$  вероятность события, состоящего в том, что ρ-алгоритм Полларда не найдет нетривиального делителя $N$$N$  за время $C\sqrt{\mathrm{\lambda <!--\; \lambda \; -->}\sqrt{N}}(\log <!--\; \; -->N{)}^2$$C{\sqrt {\lambda {\sqrt {N}}}}(\log N)^{2}$ , не превосходит величины $e^{-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->}}$$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$$N$ , $x$$x$ , и $y$$y$ , что выгодно отличает алгоритм в такой реализации от других методов факторизации чисел.

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

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

Система с распределенной памятьюПравить

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

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

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

Система с общей памятьюПравить

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