Просмотр кода страницы Ро-алгоритм Полларда

{{about|алгоритме факторизации чисел|методе дискретного логарифмирования|ро-метод Полларда для дискретного логарифмирования}}
[[Файл:Pollard rho cycle.svg|thumb|300px|Числовая последовательность зацикливается, начиная с некоторого ''n''. Цикл может быть представлен в виде греческой буквы ρ.]]
'''Ро-алгоритм''' ('''<math>\rho</math>-алгоритм''') — предложенный {{нп5|Поллард, Джон|Джоном Поллардом|en|John Pollard (mathematician)}} в [[1975 год]]у [[алгоритм]], служащий для [[факторизация|факторизации]] (разложения на множители) целых чисел. Данный алгоритм основывается на [[Алгоритм Флойда поиска длины цикла|алгоритме Флойда поиска длины цикла в последовательности]] и некоторых следствиях из [[Парадокс дней рождения|парадокса дней рождения]]. Алгоритм наиболее эффективен при факторизации [[составное число|составных чисел]] с достаточно малыми множителями в разложении. [[Вычислительная сложность|Сложность алгоритма]] оценивается как <math>O(N^{1/4})</math>{{sfn|Pollard|1974|с=521–528|name=Pollard_article}}.

ρ-алгоритм Полларда строит [[числовая последовательность|числовую последовательность]], элементы которой образуют цикл, начиная с некоторого номера ''n'', что может быть проиллюстрировано, расположением чисел в виде греческой буквы [[ро (буква)|ρ]], что послужило названием семейству алгоритмов{{sfn|Christensen|2009|loc=3.3.3.0|name=Christensen_rho}}{{sfn|Chatterjee|2008|loc=5.2.2|name=Chatterjee_rho}}.

== История алгоритма ==
В конце [[1960-е годы|60-х годов XX века]] [[Флойд, Роберт|Роберт Флойд]] придумал достаточно эффективный метод решения [[задача нахождения цикла|задачи нахождения цикла]], также известный, как алгоритм «черепаха и заяц»{{sfn|Floyd|1967|с=636–644|name=Floyd_cycle_len}}. [[Поллард, Джон|Джон Поллард]], [[Кнут, Дональд Эрвин|Дональд Кнут]] и другие математики проанализировали поведение этого алгоритма в среднем случае. Было предложено несколько модификаций и улучшений алгоритма{{sfn|Brent|1980|с=176|loc= An improved Monte Carlo factorization algorithm|name=Brent_bit_20}}.

В 1975 году Поллард опубликовал статью{{sfn|Pollard|1975|с=176|loc=A Monte Carlo method for factorization|name=Pollard_bit}}, в которой он, основываясь на алгоритме Флойда обнаружения циклов, изложил идею алгоритма факторизации чисел, работающего за время, пропорциональное <math>N^{1/4}</math><ref name="Pollard_bit" /><ref name="Pollard_article" />.
Автор алгоритма назвал его методом факторизации Монте-Карло, отражая кажущуюся случайность чисел, генерируемых в процессе вычисления. Однако позже метод всё-таки получил своё современное название — ρ-aлгоритм Полларда{{sfn|Koshy|2007|loc=Elementary Number Theory with Applications|name=Koshy}}.

В 1981 году [[Брент, Ричард|Ричард Брент]] и Джон Поллард с помощью алгоритма нашли наименьшие делители [[Числа Ферма|чисел Ферма]] <math>F_{n} = 2^{2^n}+1</math> при <math>5 \leq n \leq 13</math>{{sfn|Childs|2009|loc=A Concrete Introduction to Higher Algebra|name=Childs}}.
Скорость алгоритма сильно зависит лишь от величины наименьшего делителя исходного числа, но не от самого числа. Так, поиск наименьшего делителя седьмого числа Ферма — <math>\begin{array}{lll}F_7=  340282366920938463463374607431768211457 = 59\,649\,589\,127\,497\,217 \cdot 5\,704\,689\,200\,685\,129\,054\,721;\end{array}</math>, занимает гораздо больше времени, чем поиск делителя двенадцатого числа Ферма (т.к. его делитель 114689 значительно меньше, хотя само число состоит более чем из 1200 десятичных цифр).

В рамках проекта «{{нп5|Cunningham project|Cunningham project|en|Cunningham project}}» алгоритм Полларда помог найти делитель длиной 19 цифр числа <math>2^{2386}+1</math>. Большие делители также могли бы быть найдены, однако открытие [[Факторизация с помощью эллиптических кривых|метода факторизации с помощью эллиптических кривых]] сделало алгоритм Полларда неконкурентоспособным{{sfn|Brent|1999|loc=Some parallel algorithms for integer factorization. |name=BrentParallel}}.

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

=== Оригинальная версия ===
Рассматривается последовательность целых чисел <math>{x_{n}}</math>, такая что <math>x_{0}=2</math> и <math>x_{i+1}=(x_{i}^{2}-1\,) (\mathrm{mod}\, N)</math>, где <math>N</math> — число, которое нужно [[Факторизация целых чисел|факторизовать]]. Оригинальный [[алгоритм]] выглядит следующим образом{{sfn|Pollard|1975|loc=A Monte Carlo method for factorization|name=Pollard}}<ref name="Pollard_bit" />:

: 1. Вычисляются тройки чисел
:: <math>(x_{i}, x_{2i}, Q_{i}), i=1,2,...</math>, где <math>Q_{i} \equiv \prod_{j=1}^{i}(x_{2j}-x_{j})\, (\mathrm{mod}\, N)</math>.
:: Причём каждая такая тройка получается из предыдущей.
: 2. Каждый раз, когда число <math>i</math> кратно числу <math>m</math> (скажем, <math>m=100</math>), вычисляется [[наибольший общий делитель]] <math>d_{i}=\mathrm{GCD}(Q_{i},N)</math> любым известным методом.
: 3. Если <math>1 < d_{i} < N</math>, то частичное разложение числа <math>N</math> найдено, причём <math>N = d_{i} \times (N/d_{i})</math>.
:: Найденный делитель <math>d_{i}</math> может быть составным, поэтому его также необходимо факторизовать. Если число <math>N/d_{i}</math> составное, то продолжаем алгоритм с модулем <math>N' = N/d_{i}</math>.
: 4. Вычисления повторяются <math>S</math> раз. Если при этом число не было до конца факторизовано, выбирается, например, другое начальное число <math>x_{0}</math>.

=== Современная версия ===
Пусть <math>N</math> составное целое положительное число, которое требуется разложить на множители. Алгоритм выглядит следующим образом<ref name="Ishmuhammetov" />:
# Случайным образом выбирается небольшое число <math>x_{0}</math>{{sfn|Mollin|2006|с=215—216|name=Mollin_default_function}} и строится последовательность <math>\{x_{n}\}, n = 0, 1, 2, ...</math>, определяя каждое следующее как <math>x_{n+1} = F(x_{n})\, (\mathrm{mod}\,\, N)</math>.
# Одновременно на каждом ''i''-ом шаге вычисляется <math>d = \mathrm{GCD}(N,|x_{i}-x_{j}|)</math> для каких-либо <math>i</math>, <math>j</math> таких, что <math>j<i</math>, например, <math>i = 2j</math>.
# Если <math>d>1</math>, то вычисление заканчивается, и найденное на предыдущем шаге число <math>d</math> является делителем <math>N</math>. Если <math>N/d</math> не является простым числом, то процедуру поиска делителей продолжается, взяв в качестве <math>N</math> число <math>N'=N/d</math>.

На практике функция <math>F(x)</math> выбирается не слишком сложной для вычисления (но в то же время не линейным многочленом), при условии того, что она не должна порождать взаимно однозначное отображение. Обычно в качестве <math>F(x)</math> выбираются функции <math>F(x) = x^2 \pm 1 (\mathrm{mod}\, N)</math><ref name="Mollin_default_function" /> или <math>F(x) = x^2 \pm a (\mathrm{mod}\, N)</math><ref name="Zolotykh-rho-pollard">Золотых Н. Ю. Лекции по компьютерной алгебре. [http://www.uic.unn.ru/~zny/compalg/Lectures/ca_11_RhoPollard.pdf Лекция 11. ρ-метод Полларда.] {{Wayback|url=http://www.uic.unn.ru/~zny/compalg/Lectures/ca_11_RhoPollard.pdf |date=20141030003742 }}</ref>. Однако функции <math>x^2-2</math> и <math>x^2</math> не подходят<ref name="Pollard" />.

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

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

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

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

Поэтому нет необходимости проверять все пары <math>(x_i,x_j)</math>, а можно ограничиться парами вида <math>(x_i,x_j)</math>, где <math>j=2^k</math>, и <math>k</math> пробегает набор последовательных значений 1, 2, 3, …, а <math>i</math> принимает значения из интервала <math>[2^k+1;2^{k+1}]</math>. Например, <math>k=3</math>, <math>j=2^3=8</math>, а <math>i\in[9;16]</math>{{sfn|Ишмухаметов|2011|с=64|name=Ishmuhammetov}}.

Эта идея была предложена [[Брент, Ричард|Ричардом Брентом]] в [[1980 год]]у{{sfn|Brent|1980|с=176—184|loc=An improved Monte Carlo factorization algorithm|name=Brent_bit_20_article}} и позволяет уменьшить количество выполняемых операций приблизительно на 25 %{{sfn|Reisel|2012|loc=Selected Areas in Cryptography. Prime Numbers and Computer Methods for Factorization. 2nd ed.|name=Reisel}}.

Ещё одна вариация ρ-алгоритма Полларда была разработана [[Флойд, Роберт|Флойдом]]. Согласно Флойду, значение <math>y</math> обновляется на каждом шаге по формуле <math>y=F^2(y)=F(F(y))</math>, поэтому на шаге <math>i</math> будут получены значения <math>x_i=F^i(x_0)</math>, <math>y_i=x_{2i}=F^{2i}(x_0)</math>, и НОД на этом шаге вычисляется для <math>N</math> и <math>y-x</math><ref name="Ishmuhammetov" />.

=== Пример факторизации числа ===
Данный пример наглядно демонстрирует ρ-алгоритм факторизации (версия алгоритма, с улучшением [[Флойд, Роберт|Флойда]]), для числа ''N'' = 8051:
{| class="standard" style="text-align:center"
|+ Таблица: факторизация числа 8051
|-
!colspan="4"| ''n'' = 8051, ''F''(''x'') = (''x''<sup>2</sup> + ''1)'' mod ''n'' , ''x''<sub>0</sub> = ''y''<sub>0</sub> = 2
|-
!''i''||''x''<sub>''i''</sub>=''F''(''x''<sub>''i''-1</sub>)||''y''<sub>''i''</sub>=''F''(''F''(''y''<sub>''i''-1</sub>)) || НОД(&#124;''x''<sub>''i''</sub> − ''y''<sub>''i''</sub>&#124;, 8051)
|-
|1||5||26||1
|-
|2||26||7474||1
|-
|3||677||871||97
|}

Используя другие варианты полинома <math>F(x)</math>, можно также получить делитель 83:

{| class="standard" style="text-align:center"
|+ Таблица: факторизация числа 8051
|-
!colspan="4"| ''n'' = 8051, ''F''(''x'') = (''x''<sup>2</sup> + ''3)'' mod ''n'' , ''x''<sub>0</sub> = ''y''<sub>0</sub> = 2
|-
!''i''||''x''<sub>''i''</sub>=''F''(''x''<sub>''i''-1</sub>)||''y''<sub>''i''</sub>=''F''(''F''(''y''<sub>''i''-1</sub>)) || НОД(&#124;''x''<sub>''i''</sub> − ''y''<sub>''i''</sub>&#124;, 8051)
|-
|1||7||52||1
|-
|2||52||1442||1
|-
|3||2707||778||1
|-
|4||1442||3932||83
|}
Таким образом, ''d''<sub>''1''</sub> = 97, ''d''<sub>''2''</sub> = 83 — нетривиальные делители числа 8051.

После нахождения делителя числа, в ρ-алгоритме предлагается продолжать вычисления и искать делители числа <math>N/d</math>, если <math>N/d</math> не является простым. В этом простом примере данного шага совершать не потребовалось<ref name="Ishmuhammetov" />.

== Обоснование ρ-алгоритма Полларда ==
Алгоритм основывается на известном [[Парадокс дней рождения|парадоксе дней рождения]].

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

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

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

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

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

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

Поэтому сложность алгоритма оценивается, как <math>O(N^{1/4})</math>{{sfn|Cormen|2001|loc=Introduction to Algorithms. Section 31.9. Integer Factorization. Pollard's rho heuristic.||страница=976|name=Cormen}}. Однако в этой оценке не учитываются накладные расходы по вычислению [[Наибольший общий делитель|наибольшего общего делителя]]. Полученная сложность алгоритма, хотя и не является точной, достаточно хорошо согласуется с практикой.

Справедливо следующее утверждение: пусть <math>N</math> — [[составное число]]. Тогда существует такая константа <math>C</math>, что для любого положительного числа <math>\lambda</math> вероятность события, состоящего в том, что ρ-алгоритм Полларда не найдет нетривиального делителя <math>N</math> за время <math>C\sqrt{\lambda \sqrt N}(\log N)^2</math>, не превосходит величины <math>e^{-\lambda}</math>. Данное утверждение следует из [[Парадокс дней рождения|парадокса дней рождения]]{{sfn|Ишмухаметов|2011|с=63|name=Ishmuhammetov_BD}}.

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

  '''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));
  }

В этом варианте вычисление требует хранить в памяти всего три переменные <math>N</math>, <math>x</math>, и <math>y</math>, что выгодно отличает алгоритм в такой реализации от других методов факторизации чисел<ref name="Ishmuhammetov" />.

=== Распараллеливание алгоритма ===
Алгоритм Полларда допускает [[Распараллеливание программ|распараллеливание]] с использованием как систем с [[Разделяемая память|разделяемой памятью]], так и систем с распределенной памятью ([[Обмен сообщениями|передача сообщений]]), однако второй случай является наиболее интересным с практической точки зрения{{sfn|Косяков|2014|с=12|name=Kosyakov_advantages_of_spreded_memory}}.

==== Система с распределенной памятью ====
Существующий метод распараллеливания заключается в том, что каждый вычислительный узел исполняет один и тот же последовательный [[алгоритм]], однако, исходное число <math>x_0</math> и/или полином <math>F(x)</math> берутся различными. Для упрощения распараллеливания, предлагается получать их из генератора случайных чисел. Однако такая параллельная реализация не даёт линейного ускорения{{sfn|Kuhn|2001|с=212—229|loc=Random Walks Revisited: Extensions of Pollard’s Rho Algorithm for Computing Multiple Discrete Logarithms|name=Kuhn_lineral_tile}}.

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

[[Крэндалл, Ричард|Ричард Крэндалл]] предположил, что достижимо ускорение <math>O(P/(\log P)^2)</math>, однако данное утверждение пока не проверено{{sfn|Crandall|1999|loc=Parallelization of Polldar-rho factorization|name=Crandall}}.

==== Система с общей памятью ====
Предыдущий метод, очевидно, можно использовать и на системах с общей памятью, однако, гораздо разумнее использовать единый генератор <math>F(x)</math>{{sfn|Косяков|2014|с=19|name=Kosyakov_problems_of_spreded_memory_bottle_nack}}.

== Примечания ==
{{примечания|2}}

== Литература ==
{{refbegin|2}}
* {{книга
 |автор                 = Василенко О. Н.
 |часть                 = 
 |заглавие           = Теоретико-числовые алгоритмы в криптографии
 |оригинал           = 
 |ссылка               = http://www.ict.edu.ru/ft/002416/book.pdf
 |издание             = 
 |ответственный = 
 |место                 = М.
 |издательство   = [[МЦНМО]]
 |год                     = 2003
 |том                     = 
 |страницы           = 
 |страниц             = 328
 |isbn                       = 5-94057-103-4
 |ref                        = Василенко
}} {{Wayback|url=http://www.ict.edu.ru/ft/002416/book.pdf |date=20070127053816 }}
* {{книга
 |автор         = Ишмухаметов Ш. Т.
 |заглавие      = Методы факторизации натуральных чисел: Учебное пособие
 |ссылка        = http://old.kpfu.ru/f9/bibl/Monograph_ishm.pdf
 |место         = Казань
 |издательство  = Казанский Университет
 |год           = 2011
 |страниц       = 190
 |страницы      = 61—64
 |ref           = Ишмухаметов
|ответственный = Захаров В.М.|isbn = 978-3-659-17639-5}}
* {{Книга
|автор = Косяков М.С.
|заглавие = Введение в распределенные вычисления
|ответственный = НИУ ИТМО
|издание = 
|место = СПб
|издательство = 
|год = 2014
|страницы = 
|страниц = 155
|isbn = 
|ссылка = http://books.ifmo.ru/file/pdf/1551.pdf
|ref = Косяков}}
* {{книга
 |автор         = Герман О.Н., Нестеренко А.Ю.
 |часть         =
 |заглавие      = Теоретико-числовые методы в криптографии
 |оригинал      = 
 |ссылка        = http://new.math.msu.su/department/number/dw/lib/exe/fetch.php?media=тчмк.pdf
 |издание       = 
 |ответственный = 
 |место         = М.
 |год           = 2012
 |том           = 
 |страницы      = 
 |страниц       = 300
}}
* {{Книга|автор = Соловьёв Ю. П., [[Садовничий, Виктор Антонович|Садовничий В. А.]], [[Шавгулидзе, Евгений Тенгизович|Шавгулидзе Е. Т.]], Белокуров В. В.|заглавие = Эллиптические кривые и современные алгоритмы теории чисел|ответственный = |издание = |место = М.|издательство = Ин-т компьют. исслед.|год = 2003|страницы = |страниц = 192|isbn = ISBN 5-939722-27-X}}
* {{статья
 |автор    = Brent R. P.
 |заглавие = Некоторые параллельные алгоритмы факторизации чисел
 |оригинал = Some parallel algorithms for integer factorization
 |ссылка   = http://maths-people.anu.edu.au/~brent/pd/rpb193.pdf
 |язык     = англ.
 |год      = 1999
 |страницы = 7
 |doi      = 10.1017/S0305004100049252
 |ref      = Brent
}}
* {{Статья
|автор = Brent R. P.
|год = 1980
|месяц = 06
|число = 01
|doi = 10.1007/BF01933190
|issn = 1572-9125
|выпуск = 2
|язык = en
|страницы = 176—184
|издание = BIT Numerical Mathematics
|заглавие = An improved Monte Carlo factorization algorithm
|ссылка = https://link.springer.com/article/10.1007/BF01933190
|том = 20
|ref = Brent}}
* {{Статья
|автор = Chatterjee S., Sarkar P.
|год = 2008
|isbn = 978-1-59693-238-8
|язык = en
|страниц = 232
|место = Boston
|заглавие = Introduction
|ссылка = https://www.amazon.com/Introduction-Identity-Based-Encryption-Information-Security/dp/1596932384
|издательство = Springer US
|издание = Identity-Based Encryption
|ref = Chatterjee}}
* {{книга
 |автор         = Childs, Lindsay N.
 |часть         = Congruences
 |заглавие      = Введение в высшую алгебру
 |оригинал      = Concrete Introduction to Higher Algebra
 |ссылка        = https://books.google.ru/books/about/A_Concrete_Introduction_to_Higher_Algebr.html?id=qyDAKBr_I2YC&redir_esc=y
 |издание       = 3-е изд
 |место         = USA
 |издательство  = Springer
 |год           = 2009
 |страницы      = 471—473
 |страниц       = 603
 |isbn          = 978-0-387-74725-5
 |ref           = Childs
}}
* {{Статья
|автор = Chris Christensen
|год = 2009
|месяц = 01
|число = 27
|doi = 10.1080/01611190802293397
|issn = 0161-1194
|выпуск = 1
|страниц = 236
|издание = Cryptologia
|заглавие = Review of Modern Cryptanalysis: Techniques for Advanced Code Breaking by Christopher Swenson
|ссылка = https://dx.doi.org/10.1080/01611190802293397
|том = 33
|ref = Christensen}}
* {{книга
 |автор         = Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.
 |заглавие      = Алгоритмы: построение и анализ
 |оригинал      = Introduction to algorithms
 |ссылка        = https://books.google.ru/books?id=NLngYyWFl_YC
 |издание       = 2-е изд
 |место         = USA
 |издательство  = MIT Press
 |год           = 2001
 |страницы      = 897—907
 |страниц       = 1180
 |isbn          = 9780262032933
 |ref           = Cormen
}}
* {{статья
 |автор       = Crandall R.E.
 |заглавие = Распараллеливание P-алгоритма факторизации Полларда
 |оригинал = Parallelization of Polldar-rho factorization
 |ссылка     = http://people.reed.edu/~crandall/papers/parrho.pdf
 |язык         = англ.
 |год           = 1999
 |ref              = Crandall
 |издание   = 
 |archiveurl       = https://web.archive.org/web/20100706141942/http://people.reed.edu/~crandall/papers/parrho.pdf
 |archivedate      = 2010-07-06
}}
* {{книга
 |автор         = Koshy T.
 |часть         = Congruences
 |заглавие      = Элементарная теория чисел и её приложения
 |оригинал      = Elementary Number Theory with Applications
 |ссылка        = https://books.google.ru/books?id=d5Z5I3gnFh0C
 |издание       = 2-е изд
 |место         = USA
 |издательство  = Academic Press
 |год           = 2007
 |страницы      = 238
 |страниц       = 771
 |isbn          = 9780123724878
 |ref           = Koshy
}}
* {{Статья
|автор = Kuhn F., Struik R.
|ответственный = Serge Vaudenay, Amr M.
|год = 2001
|doi = 10.1007/3-540-45537-x_17
|isbn = 978-3-540-43066-7, 978-3-540-45537-0
|язык = en
|страницы = 212—229
|заглавие = Random Walks Revisited: Extensions of Pollard’s Rho Algorithm for Computing Multiple Discrete Logarithms
|ссылка = https://link.springer.com/chapter/10.1007/3-540-45537-X_17
|издательство = Springer Berlin Heidelberg
|издание = Selected Areas in Cryptography
|ref= Kuhn}}
* {{Книга
|автор = Mollin R.A.
|заглавие = An Introduction to Cryptography
|ответственный = Rosen K.H.
|издание = 2
|место = London
|издательство = Chapman and Hall
|год = 2006
|страниц = 413
|isbn = 9781584886181
|ссылка = http://antoanthongtin.vn/portals/0/uploadimages/kiennt2/sach/sach-csdl4/1584886188.pdf
|ref = Mollin
|access-date = 2015-11-04
|archive-date = 2016-03-04
|archive-url = https://web.archive.org/web/20160304103729/http://antoanthongtin.vn/portals/0/uploadimages/kiennt2/sach/sach-csdl4/1584886188.pdf
|url-status = dead
}}
* {{статья
 |автор=Pollard J. M.
 |год=1975
 |заглавие=A Monte Carlo method for factorization
 |издание=BIT Numerical Mathematics
 |volume=15
 |номер=3
 |pages=331–334
 |ссылка=http://www.cs.cmu.edu/~avrim/451f11/lectures/lect1122_Pollard.pdf
 |issn=
 |ref=Pollard
}}
* {{Статья
|автор = Pollard J.M.
|год = 1974
|doi = 10.1017/S0305004100049252
|issn = 1469-8064
|выпуск = 03
|страницы = 521–528
|издание = Mathematical Proceedings of the Cambridge Philosophical Society
|заглавие = Theorems on factorization and primality testing
|ссылка = http://journals.cambridge.org/article_S0305004100049252
|том = 76
}}
* {{статья
 |автор    = Pollard J. M.
 |заглавие = Методы факторизации и проверка простоты.
 |оригинал = Theorems on factorization and primality testing.
 |ссылка   = http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=2074504
 |язык     = англ.
 |издание  = Математические Труды Кэмбриджского Философского Общества (Mathematical Proceedings of the Cambridge Philosophical Society)
 |год      = 1974
 |том      = 76
 |номер    = 3
 |страницы = 521
 |doi      = 10.1017/S0305004100049252
 |ref      = Pollard
}}
* {{книга
 |автор         = Reisel, H.
 |заглавие      = Простые числа и компьютерные методы факторизации
 |оригинал      = Prime Numbers and Computer Methods for Factorization
 |ссылка        = https://books.google.ru/books?id=94DaZuVETzIC
 |издание       = 2-е изд
 |место         = USA
 |издательство  = Springer
 |год           = 2012
 |страницы      = 183
 |страниц       = 464
 |isbn          = 978-0-8176-8297-2
 |ref           = Reisel
}}
* {{Статья
|автор = Robert W. Floyd
|год = 1967
|doi = 10.1145/321420.321422
|issn = 0004-5411
|выпуск = 4
|страницы = 636–644
|издание = J. ACM
|заглавие = Nondeterministic Algorithms
|ссылка = http://doi.acm.org/10.1145/321420.321422
|том = 14
|ref= Floyd}}
{{refend}}

{{Теоретико-числовые алгоритмы}}
{{Добротная статья|Математика}}

[[Категория:Алгоритмы факторизации]]