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

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

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

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

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

В 1981 году Ричард Брент и Джон Поллард с помощью алгоритма нашли наименьшие делители чисел Ферма ${\displaystyle F_{n}=2^{2^{n}}+1}$ при ${\displaystyle 5\leq n\leq 13}$ . Скорость алгоритма сильно зависит лишь от величины наименьшего делителя исходного числа, но не от самого числа. Так, поиск наименьшего делителя седьмого числа Ферма — ${\displaystyle {\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 десятичных цифр).

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

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

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

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

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

${\displaystyle (x_{i},x_{2i},Q_{i}),i=1,2,...}$ , где ${\displaystyle Q_{i}\equiv \prod _{j=1}^{i}(x_{2j}-x_{j})\,(\mathrm {mod} \,N)}$ .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

n = 8051, F ( x ) = ( x 2 + 1) mod n , x 0 = y 0 = 2
i	x i = F ( x i -1 )	y i = F ( F ( y i -1 ))	НОД(| x i − y i |, 8051)
1	5	26	1
2	26	7474	1
3	677	871	97

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

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

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

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

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

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

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

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

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

Пусть последовательность ${\displaystyle \{u_{n}\}}$ состоит из разностей ${\displaystyle x_{i}-x_{j}}$ , проверяемых в ходе работы алгоритма. Определяется новая последовательность ${\displaystyle \{z_{n}\}}$ , где ${\displaystyle z_{n}=u_{n}\,\mathrm {mod} \,q}$ , ${\displaystyle q}$ — меньший из делителей числа ${\displaystyle N}$ .

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

Если ${\displaystyle z_{i}=z_{j}}$ , тогда ${\displaystyle x_{i}-x_{j}\equiv 0\,\mathrm {mod} \,q}$ , то есть, ${\displaystyle x_{i}-x_{j}=kq}$ для некоторого целого ${\displaystyle k}$ . Если ${\displaystyle x_{i}\neq x_{j}}$ , что выполняется с большой вероятностью, то искомый делитель ${\displaystyle q}$ числа ${\displaystyle N}$ будет найден как ${\displaystyle \mathrm {GCD} (N,|x_{i}-x_{j}|)}$ . Поскольку ${\displaystyle {\sqrt {q}}\leq n^{1/4}}$ , то с вероятностью, превышающей ${\displaystyle 1/2}$ , делитель ${\displaystyle N}$ будет найден за ${\displaystyle 1.18\times N^{1/4}}$ итераций .

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

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

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

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

В этом варианте вычисление требует хранить в памяти всего три переменные ${\displaystyle N}$ , ${\displaystyle x}$ , и ${\displaystyle y}$ , что выгодно отличает алгоритм в такой реализации от других методов факторизации чисел .

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

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

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

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

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

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

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

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

Примечания

Литература