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

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

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

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

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

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

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

В 1981 году Ричард Брент и Джон Поллард с помощью алгоритма нашли наименьшие делители чисел Ферма $F_n=2^{2^n}+1$ при $5\le n\le 13$Шаблон:Sfn. Скорость алгоритма сильно зависит лишь от величины наименьшего делителя исходного числа, но не от самого числа. Так, поиск наименьшего делителя седьмого числа Ферма — $\begin{array}{c}{F}_7=340282366920938463463374607431768211457=59649589127497217\cdot 5704689200685129054721;\end{array}$, занимает гораздо больше времени, чем поиск делителя двенадцатого числа Ферма (т.к. его делитель 114689 значительно меньше, хотя само число состоит более чем из 1200 десятичных цифр).

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

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

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

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

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

$(x_i,x_{2i},Q_i),i=1,2,...$, где $Q_i\equiv \prod _{j=1}^i(x_{2j}-x_j)(\mathrm{m}\mathrm{o}\mathrm{d}N)$.

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

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

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

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

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

Современная версия

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

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

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

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

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

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

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

Пусть $F(x)=(x^2-1)modN$. Тогда, если $(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]$Шаблон:Sfn.

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

Ещё одна вариация ρ-алгоритма Полларда была разработана Флойдом. Согласно Флойду, значение $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:

Таблица: факторизация числа 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)$, можно также получить делитель 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$ не является простым. В этом простом примере данного шага совершать не потребовалось.

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

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

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

Пусть последовательность $\{u_n\}$ состоит из разностей $x_i-x_j$, проверяемых в ходе работы алгоритма. Определяется новая последовательность $\{z_n\}$, где $z_n=u_n\mathrm{m}\mathrm{o}\mathrm{d}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{m}\mathrm{o}\mathrm{d}q$, то есть, $x_i-x_j=kq$ для некоторого целого $k$. Если $x_i\ne x_j$, что выполняется с большой вероятностью, то искомый делитель $q$ числа $N$ будет найден как $\mathrm{G}\mathrm{C}\mathrm{D}(N,|x_i-x_j|)$. Поскольку $\sqrt{q}\le 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})$Шаблон:Sfn. Однако в этой оценке не учитываются накладные расходы по вычислению наибольшего общего делителя. Полученная сложность алгоритма, хотя и не является точной, достаточно хорошо согласуется с практикой.

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

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

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

 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$, что выгодно отличает алгоритм в такой реализации от других методов факторизации чисел.

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

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

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

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

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

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

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

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

Литература

• Шаблон:Книга Шаблон:Wayback
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья