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

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

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


 В конце 60-х годов XX века Роберт Флойд придумал достаточно эффективный решения задачи нахождения цикла, также известный, как алгоритм «черепаха и заяц». Джон Поллард, Дональд Кнут и другие математики проанализировали поведение этого алгоритма в среднем случае. Было предложено несколько модификаций и улучшений алгоритма.
 В 1975 году Поллард опубликовал статью, в которой он, основываясь на алгоритме Флойда обнаружения циклов, изложил идею алгоритма факторизации чисел, работающего за время, пропорциональное N1/4. Автор алгоритма назвал его методом факторизации Монте-Карло, отражая кажущуюся случайность чисел, генерируемых в процессе вычисления. Однако позже метод всё-таки получил своё современное название — ρ-aлгоритм Полларда.
 В 1981 году Ричард Брент и Джон Поллард с помощью алгоритма нашли наименьшие делители чисел Ферма Fn=22n+1 при 5n13.
 Так, F8=1238926361552897p62, где p62 — простое число, состоящее из 62 десятичных цифр.
 В рамках проекта «» алгоритм Полларда помог найти делитель длиной 19 цифр числа 22386+1. Большие делители также могли бы быть найдены, однако открытие метода факторизации с помощью эллиптических кривых сделало алгоритм Полларда неконкурентоспособным.

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


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


 Рассматривается последовательность целых чисел xn, такая что x0=2 и xi+1=(xi21)(modN), где N — число, которое нужно факторизовать. Оригинальный алгоритм выглядит следующим образом:

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

(xi,x2i,Qi),i=1,2,..., где Qij=1i(x2jxj)(modN).
 Причём каждая такая тройка получается из предыдущей.
  2. Каждый раз, когда число i кратно числу m (скажем, m=100), вычисляется наибольший общий делитель di=GCD(Qi,N) любым известным методом.
 3. Если 1<di<N, то частичное разложения числа N найдено, причём N=di×(N/di).

  Найденный делитель di может быть составным, поэтому его также необходимо факторизовать. Если число N/di составное, то продолжаем алгоритм с модулем N=N/di.
  4. Вычисления повторяются S раз. Если при этом число не было до конца факторизовано, выбирается, например, другое начальное число x0.

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


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

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

 На практике функция F(x) выбирается не слишком сложной для вычисления (но в то же время не линейным многочленом), при условии того, что она не должна порождать взаимно однозначное отображение. Обычно в качестве F(x) выбираются функции F(x)=x2±1(modN) или F(x)=x2±a(modN). Однако функции x22 и x2 не подходят.
 Если известно, что для делителя p числа N справедливо p1(modk) при некотором k>2, то имеет смысл использовать F(x)=xk+b.
 Существенным недостатком алгоритма в такой реализации является необходимость хранить большое число предыдущих значений xj.

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


 Изначальная версия алгоритма обладает рядом недостатков. В настоящий момент существует несколько подходов к улучшению оригинального алгоритма.
 Пусть F(x)=(x21)modN. Тогда, если (xjxi)0(modp), то (f(xj)f(xi))0(modp), поэтому, если пара (xi,xj) даёт решение, то решение даст любая пара (xi+k,xj+k).
 Поэтому, нет необходимости проверять все пары (xi,xj), а можно ограничиться парами вида (xi,xj), где j=2k, и k пробегает набор последовательны значений 1, 2, 3, \ldots, а i принимает значения из интервала [2k+1;2k+1]. Например, k=3, j=23=8, а i[9;16].
 Эта идея была предложена Ричардом Брентом в 1980 году и позволяет уменьшить количество выполняемых операций приблизительно на 25  Ещё одна вариация ρ-алгоритма Полларда была разработана Флойдом. Согласно Флойду, значение y обновляется на каждом шаге по формуле y=F2(y)=F(F(y)), поэтому на шаге i будут получены значения xi=Fi(x0), yi=x2i=F2i(x0), и НОД на этом шаге вычисляется для N и yx.

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


 Данный пример наглядно демонстрирует ρ-алгоритм факторизации (версия алгоритма, с улучшением Флойда), для числа N = 8051:
 n = 8051,   F(x) = (x2 + 3) mod n ,   x0 = y0 = 2
i
1
2
3
4

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

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


 Алгоритм основывается на известном парадоксе дней рождения.
 Следует отметить, что вероятность p=0.5 в парадоксе дней рождения достигается при λ0.69.
 Пусть последовательность {un} состоит из разностей xixj, проверяемых в ходе работы алгоритма. Определяется новая последовательность {zn}, где zn=unmodq, q — меньший из делителей числа N.
 Все члены последовательности {zn} меньше N. Если рассматривать её как случайную последовательность целых чисел, меньших q, то, согласно парадоксу дней рождения, вероятность того, что среди l+1 её членов попадутся два одинаковых, превысит 1/2 при λ0.69, тогда l должно быть не меньше 2λq1.4q1.18q.
 Если zi=zj, тогда xixj0modq, то есть, xixj=kq для некоторого целого k. Если xixj, что выполняется с большой вероятностью, то искомый делитель q числа N будет найден как GCD(N,|xixj|). Поскольку qn1/4, то с вероятностью, превышающей 1/2 , делитель N будет найден за 1.18×N1/4 итераций.

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


 Чтобы оценить сложность алгоритма, рассматривается последовательность, строящаяся в процессе вычислений, как случайная (разумеется, ни о какой строгости при этом говорить нельзя). Чтобы полностью факторизовать число N длиной β бит, достаточно найти все его делители, не превосходящие N, что требует максимум порядка N арифметических операций, или N1/4β2=2β/4β2 битовых операций.
 Поэтому сложность алгоритма оценивается, как O(N1/4). Однако в этой оценке не учитываются накладные расходы по вычислению наибольшего общего делителя. Полученная сложность алгоритма, хотя и не является точной, достаточно хорошо согласуется с практикой.
 Справедливо следующее утверждение: пусть N — составное число. Тогда существует такая константа C, что для любого положительного числа λ вероятность события, состоящего в том, что ρ-алгоритм Полларда не найдет нетривиального делителя N за время CλN(logN)2, не превосходит величины eλ. Данное утверждение следует из парадокса дней рождения.

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


 Объём памяти, используемый алгоритмом, можно значительно уменьшить.
 \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Система с распределенной памятью
 Существующий метод распалаллеливания заключается в том, что каждый вычислительный узел исполняет один и тот же последовательный алгоритм, однако, исходное число x0 и/или полином F(x) берутся различными. Для упрощения распаралеливания, предлагается получать их из генератора случайных чисел. Однако такая параллельная реализация не даёт линейного ускорения.
 Предположим что есть P одинаковых исполнителей. Если мы используем P различных последовательностей (то есть различных полиномов F(x)), то вероятность того, что первые k чисел в этих последовательностях будут различными по модулю p будет примерно равна exp(k2P/2p). Таким образом, максимальное ускорение можно оценить как P1/2.
 Ричард Крэндалл предположил, что достижимо ускорение O(P/(logP)2), однако данное утверждение пока не проверено.

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