Processing math: 100%

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

Ро-алгоритм (ρ-алгоритм) — предложенный в 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=(x2i1)(modN), где N —число, которое нужно факторизовать. Оригинальный алгоритм выглядитследующим образом:

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

(xi,x2i,Qi),i=1,2,..., гдеQiij=1(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).