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

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

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

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

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

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

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

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

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

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

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

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

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

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}$ составное целое положительное число, которое требуется разложить на множители. Алгоритм выглядит следующим образом[11]:

1. Случайным образом выбирается небольшое число ${\displaystyle x_{0}}$[12] и строится последовательность ${\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)}$[12] или ${\displaystyle F(x)=x^{2}\pm a(\mathrm {mod} \,N)}$[13]. Однако функции ${\displaystyle x^{2}-2}$ и ${\displaystyle x^{2}}$ не подходят[10].

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

Существенным недостатком алгоритма в такой реализации является необходимость хранить большое число предыдущих значений ${\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]}$[11].

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

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

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

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

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

n = 8051, F(x) = (x^2 + 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

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

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

n = 8051, F(x) = (x^2 + 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.

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

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

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

Парадокс дней рождений, кратко:
Пусть ${\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}}$ итераций[11].

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

Чтобы оценить сложность алгоритма, рассматривается последовательность, строящаяся в процессе вычислений, как случайная (разумеется, ни о какой строгости при этом говорить нельзя). Чтобы полностью факторизовать число ${\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})}$[16]. Однако в этой оценке не учитываются накладные расходы по вычислению наибольшего общего делителя. Полученная сложность алгоритма, хотя и не является точной, достаточно хорошо согласуется с практикой.

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

1. Pollard, 1974, с. 521–528.
2. Christensen, 2009, 3.3.3.0.
3. Chatterjee, 2008, 5.2.2.
4. Floyd, 1967, с. 636–644.
5. Brent, 1980, An improved Monte Carlo factorization algorithm, с. 176.
6. Pollard, 1975, A Monte Carlo method for factorization, с. 176.
7. Koshy, 2007, Elementary Number Theory with Applications.
8. Childs, 2009, A Concrete Introduction to Higher Algebra.
9. Brent, 1999, Some parallel algorithms for integer factorization..
10. Pollard, 1975, A Monte Carlo method for factorization.
11. Ишмухаметов, 2011, с. 64.
12. Mollin, 2006, с. 215—216.
13. Золотых Н. Ю. Лекции по компьютерной алгебре. Лекция 11. ρ-метод Полларда. Архивная копия от 30 октября 2014 на Wayback Machine
14. Brent, 1980, An improved Monte Carlo factorization algorithm, с. 176—184.
15. Reisel, 2012, Selected Areas in Cryptography. Prime Numbers and Computer Methods for Factorization. 2nd ed..
16. Cormen, 2001, Introduction to Algorithms. Section 31.9. Integer Factorization. Pollard's rho heuristic..
17. Ишмухаметов, 2011, с. 63.
18. Косяков, 2014, с. 12.
19. Kuhn, 2001, Random Walks Revisited: Extensions of Pollard’s Rho Algorithm for Computing Multiple Discrete Logarithms, с. 212—229.
20. Crandall, 1999, Parallelization of Polldar-rho factorization.
21. Косяков, 2014, с. 19.

Литература

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4. Архивная копия от 27 января 2007 на Wayback Machine
• Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: Учебное пособие / Захаров В.М.. — Казань: Казанский Университет, 2011. — С. 61—64. — 190 с. — ISBN 978-3-659-17639-5.
• Косяков М.С. Введение в распределенные вычисления / НИУ ИТМО. — СПб., 2014. — 155 с.
• Герман О.Н., Нестеренко А.Ю. Теоретико-числовые методы в криптографии. — М., 2012. — 300 с.
• Соловьёв Ю. П., Садовничий В. А., Шавгулидзе Е. Т., Белокуров В. В. Эллиптические кривые и современные алгоритмы теории чисел. — М.: Ин-т компьют. исслед., 2003. — 192 с. — ISBN ISBN 5-939722-27-X.
• Brent R. P. Некоторые параллельные алгоритмы факторизации чисел (англ.) = Some parallel algorithms for integer factorization. — 1999. — С. 7. — doi:10.1017/S0305004100049252.
• Brent R. P. An improved Monte Carlo factorization algorithm (англ.) // BIT Numerical Mathematics. — 1980. — 1 June (vol. 20, iss. 2). — P. 176—184. — ISSN 1572-9125. — doi:10.1007/BF01933190.
• Chatterjee S., Sarkar P. Introduction (англ.) // Identity-Based Encryption. — Boston: Springer US, 2008. — ISBN 978-1-59693-238-8.
• Childs, Lindsay N. Congruences // Введение в высшую алгебру = Concrete Introduction to Higher Algebra. — 3-е изд. — USA: Springer, 2009. — С. 471—473. — 603 с. — ISBN 978-0-387-74725-5.
• Chris Christensen. Review of Modern Cryptanalysis: Techniques for Advanced Code Breaking by Christopher Swenson // Cryptologia. — 2009. — 27 января (т. 33, вып. 1). — ISSN 0161-1194. — doi:10.1080/01611190802293397.
• Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Алгоритмы: построение и анализ = Introduction to algorithms. — 2-е изд. — USA: MIT Press, 2001. — С. 897—907. — 1180 с. — ISBN 9780262032933.
• Crandall R.E. Распараллеливание P-алгоритма факторизации Полларда (англ.) = Parallelization of Polldar-rho factorization. — 1999. Архивировано 6 июля 2010 года.
• Koshy T. Congruences // Элементарная теория чисел и её приложения = Elementary Number Theory with Applications. — 2-е изд. — USA: Academic Press, 2007. — С. 238. — 771 с. — ISBN 9780123724878.
• Kuhn F., Struik R. Random Walks Revisited: Extensions of Pollard’s Rho Algorithm for Computing Multiple Discrete Logarithms (англ.) // Selected Areas in Cryptography / Serge Vaudenay, Amr M.. — Springer Berlin Heidelberg, 2001. — P. 212—229. — ISBN 978-3-540-43066-7, 978-3-540-45537-0. — doi:10.1007/3-540-45537-x_17.
• Mollin R.A. An Introduction to Cryptography / Rosen K.H.. — 2. — London: Chapman and Hall, 2006. — 413 с. — ISBN 9781584886181. Архивировано 4 марта 2016 года.
• Pollard J. M. A Monte Carlo method for factorization // BIT Numerical Mathematics. — 1975. — Vol. 15, № 3. — P. 331–334.
• Pollard J.M. Theorems on factorization and primality testing // Mathematical Proceedings of the Cambridge Philosophical Society. — 1974. — Т. 76, вып. 03. — С. 521–528. — ISSN 1469-8064. — doi:10.1017/S0305004100049252.
• Pollard J. M. Методы факторизации и проверка простоты. (англ.) = Theorems on factorization and primality testing. // Математические Труды Кэмбриджского Философского Общества (Mathematical Proceedings of the Cambridge Philosophical Society). — 1974. — Т. 76, № 3. — С. 521. — doi:10.1017/S0305004100049252.
• Reisel, H. Простые числа и компьютерные методы факторизации = Prime Numbers and Computer Methods for Factorization. — 2-е изд. — USA: Springer, 2012. — С. 183. — 464 с. — ISBN 978-0-8176-8297-2.
• Robert W. Floyd. Nondeterministic Algorithms // J. ACM. — 1967. — Т. 14, вып. 4. — С. 636–644. — ISSN 0004-5411. — doi:10.1145/321420.321422.