Перегляд вихідного коду сторінки Ρ-алгоритм Полларда

{{DISPLAYTITLE:ρ-алгоритм Полларда}}
{{не плутати|алгоритм (p-1)|алгоритмом (p-1), який також розробив Джон Поллард}} 
[[Файл:Pollard rho cycle.svg|thumb|300px|Числова послідовність зациклюється, починаючи з деякого ''n''. Цикл виглядає як грецька [[Ро (літера)|літера ρ]].]]
'''ρ-алгоритм Полларда''' — алгоритм [[Факторизація цілих чисел|факторизації цілих чисел]], що ґрунтується на [[Алгоритм Флойда пошуку циклу в послідовності|пошуку циклу в послідовності]] і деяких наслідках із [[Парадокс днів народження|парадоксу днів народжень]]. Його запропонував {{Не перекладено|Джон Поллард|Джон Поллард|en|John Pollard (mathematician)}} (1975). Алгоритм найбільш ефективний для факторизації [[Складене число|складених чисел]] із досить малими множниками в розкладі. [[Обчислювальна складність]] оцінюється як <math>O(N^{1/4})</math>.

У всіх варіантах ρ-алгоритму Полларда будується [[числова послідовність]], елементи якої, починаючи з деякого номера ''n'', утворюють цикл, що можна проілюструвати розташуванням членів послідовності у вигляді грецької [[Ро (літера)|літери ρ]]. Це й послужило назвою для сімейства методів.

== Історія алгоритму ==
Наприкінці [[1960-ті|60-х років]] [[XX століття]] Дональд Кнут опублікував досить ефективний [[алгоритм Флойда пошуку циклу в послідовності|алгоритм пошуку циклу в послідовності]], також відомий, як алгоритм «черепаха та заєць», який він пов'язував з ім'ям Флойда<ref>Перший опис алгоритму «черепахи та зайця» з'явився в другому томі [[Мистецтво програмування|Мистецтва програмування]] Дональда Кнута ({{citation|first=Donald E.|last=Knuth|authorlink=Дональд Кнут|title=The Art of Computer Programming, vol. II: Seminumerical Algorithms|publisher=Addison-Wesley|year=1969}}), у вправах 6 та 7 (стор. 7). На сторінці 4 Кнут приписує цей алгоритм Флойду, не посилаючись на джерела. Хоча Флойд і опублікував 1967 року статтю: {{citation|last=Floyd|first=R.W.|authorlink=Роберт Флойд|title=Non-deterministic Algorithms|journal=J. ACM|pages=636–644|volume=14|issue=4|year=1967|url=http://doi.acm.org/10.1145/321420.321422|doi=10.1145/321420.321422}}, однак у ній він описав алгоритми пошуку простих циклів в [[Орієнтований граф|орієнтованому графі]].</ref>. {{Не перекладено|Джон Поллард|Джон Поллард|en|John Pollard (mathematician)}}, [[Дональд Кнут]] та інші математики проаналізували поведінку цього алгоритму в середньому випадку. Було запропоновано кілька модифікацій та поліпшень алгоритму.

У [[1975|1975 році]] Поллард опублікував статтю, в якій він, ґрунтуючись на алгоритмі Флойда виявлення циклів, виклав ідею алгоритму факторизації чисел, який виконується за час, пропорційний <math>N^{1/4}</math>{{sfn|Brent|1980|loc=An Improved Monte Carlo Factorization Algorithm|name=Brent}}.
Автор назвав його методом факторизації Монте-Карло, тому, що в процесі обчислення генерується [[псевдовипадкова послідовність]] чисел. Проте пізніше метод все-таки назвали ρ-алгоритмом Полларда{{sfn|Koshy|2007|loc=Elementary Number Theory with Applications|name=Koshy}}.

У [[1981|1981 році]] {{Не перекладено|Річард Брент||ru|Брент, Ричард}} і Джон Поллард за допомогою цього алгоритму знайшли менший дільник восьмого [[Числа Ферма|числа Ферма]] <math>F_{8} = 2^{2^8}+1</math>{{sfn|Childs|2009|loc=471-473|name=A Concrete Introduction to Higher Algebra}}.

Так, <math>F_8 = 1238926361552897 \cdot p_{62}</math>, де <math>p_{62}</math> — просте число, що складається з 62 десяткових цифр.

У межах проекту «{{нп|Cunningham project}}» алгоритм Полларда допоміг знайти дільник числа <math>2^{2386}+1</math> довжиною 19 цифр. Більші дільники також можна б знайти, але відкриття {{Не перекладено| Факторизація за допомогою еліптичних кривих| методу факторизації за допомогою еліптичних кривих|ru|Факторизация с помощью эллиптических кривых}} зробило алгоритм Полларда неконкурентоспроможним{{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>&nbsp;— число, яке потрібно факторизувати. Оригінальний алгоритм виглядає таким чином{{sfn|Pollard|1975|loc=A Monte Carlo method for factorization|name=Pollard}}.

: 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>i = S = 10^5</math>. Якщо при цьому число не було до кінця факторизовано, можна вибрати, наприклад, інше початкове число <math>x_{0}</math>.

=== Сучасна версія ===
Нехай <math>N</math> складене ціле [[додатне число]], яке потрібно розкласти на множники. Алгоритм виглядає таким чином:{{sfn|Ішмухаметов|2011|с=64|name=Ishmuhammetov}}
# Вибираємо невелике число <math>x_{0}</math> та будуємо [[послідовність]] <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> або <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. ρ-метод Полларда.] {{Webarchive|url=https://web.archive.org/web/20141030003742/http://www.uic.unn.ru/~zny/compalg/Lectures/ca_11_RhoPollard.pdf |date=30 жовтня 2014 }}</ref>. Однак не слід застосовувати функції <math>x^2-2</math> та <math>x^2</math>{{sfn|Pollard|1975|loc=A Monte Carlo method for factorization|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>{{sfn|Pollard|1975|loc=A Monte Carlo method for factorization|name=Pollard}}.

Істотним недоліком алгоритму в такий реалізації є необхідність зберігати велику кількість попередніх значень <math>x_{j}</math>.

=== Покращення алгоритму ===
Початкова версія алгоритму має низку недоліків. На даний момент{{коли?}} існує кілька підходів до поліпшення оригінального методу.

Нехай <math>F(x) = (x^2 - 1) \mathrm{mod}\, N</math>. Зауважимо, що й <math>(x_{j} - x_{i}) \equiv 0 (\mathrm{mod}\, p)</math>, то <math>(f(x_{j}) - f(x_{i})) \equiv 0 (\mathrm{mod}\, 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|loc=Методи факторизації натуральних чисел: Навчальний посібник|name=Ishmuhammetov}}.

Цю ідею запропонував {{Не перекладено|Річард Брент||ru|Брент, Ричард}} у [[1980|1980 році]]{{sfn|Brent|1980|p=176-184}} і вона дозволяє зменшити кількість виконуваних операцій приблизно на чверть (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>, тому на кроці ''i'' будуть отримані значення <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>{{sfn|Ішмухаметов|2011|с=64|name=Ishmuhammetov}}.

=== Приклад факторизації числа ===
Нехай <math>N = 8051</math>, <math>F(x) = (x^2 + 1)\, \mathrm{mod}\, 8051</math>, <math>x_0=y_0=2</math>, <math>y_{i+1}=F(F(y_{i}))</math>.

{|border=1 class="wikitable" style="text-align: center;"
! width=30|''i''||width=60|''x''<sub>''i''</sub>||width=60|''y''<sub>''i''</sub>||width=150|НСД (|''x''<sub>''i''</sub> −''y''<sub>''i''</sub>|, 8051)
|-
|1||5||26||1
|-
|2||26||7474||1
|-
|3||677||871||97
|}

Таким чином, 97 — нетривіальний дільник числа 8051. Використовуючи інші варіанти поліному <math>F(x)</math>, можна також отримати дільник 83.

== Обґрунтування ρ-методу Полларда ==
Алгоритм ґрунтується на відомому парадоксі днів народження.

'''Теорема''' ([[Парадокс днів народження]])

{{теорема|Нехай <math>\lambda > 0</math>. Для випадкової вибірки з <math>l+1</math> елементів, кожний з яких менший від <math>q</math>, де <math>l = \sqrt{2 \lambda q}</math>, ймовірність того, що два елементи виявляться однаковими <math>p > 1 - \exp^{-\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>&nbsp;— менший з дільників числа <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} \leqslant n^{1/4}</math>, то з імовірністю, що перевищує 0,5, дільник <math>N</math> буде знайдено за <math>1.18 \times N^{1/4}</math> ітерацій{{sfn|Ішмухаметов|2011|с=64|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>. Ця теорема випливає з [[Парадокс днів народження|парадоксу днів народження]].

== Особливості реалізації ==
Обсяг пам'яті, використовуваний алгоритмом, можна значно зменшити.

  '''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>, що вигідно відрізняє метод в такій реалізації від інших методів факторизації чисел{{sfn|Ішмухаметов|2011|с=64|name=Ishmuhammetov}}.

=== Розпаралелювання алгоритму ===
Алгоритм Полларда дозволяє [[Розпаралелювання програм|розпаралелювання]] з використанням будь-якого стандарту паралельних обчислень (наприклад, [[OpenMP]] та ін.).

Існує декілька варіантів розпаралелювання, але їх спільна ідея полягає в тому, що кожний [[процесор]] виконує послідовний алгоритм, причому початкове число <math>x_{0}</math> та/або поліном <math>F(x)</math> мають бути різними для кожного процесора. Очікується, що на якомусь процесорі початкові параметри (випадково) виявляться більш вдалими і дільник буде знайдено швидше, однак цей випадок недетермінований (імовірнісний). Прискорення від такої паралельної реалізації значно менше лінійного.

Припустимо, що є <math>P</math> однакових процесорів. Якщо ми використовуємо <math>P</math> різних послідовностей (тобто, різних поліномів <math>F(x)</math>), то ймовірність того, що перші <math>k</math> чисел в цих послідовностях будуть різними за модулем <math>p</math> приблизно дорівнює <math>\exp({-k^2 P}/{2 p})</math>. Таким чином, прискорення можна оцінити як <math>P^{1/2}</math>{{sfn|Brent|1999|loc=Some parallel algorithms for integer factorization. |name=BrentParallel}}.
Тобто, збільшення швидкості вдвічі можна очікувати, якщо процесорів буде вчетверо більше.

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

== Див. також ==
* [[Метод Монте-Карло]]

== Примітки ==
{{примітки}}

== Література ==
* {{книга 
|автор         = Ішмухаметов Ш. Т. 
|заголовок      = Методи факторизації натуральних чисел: Навчальний посібник 
|посилання        = http://old.kpfu.ru/f9/bibl/Monograph_ishm.pdf
|місце         = Казань 
|видавництво = Казанський Університет 
|рік           = 2011 
|сторінок       = 190 
|сторінки      = 61-64 
|ref           = Ішмухаметов 
}}
* {{книга 
|автор         = Василенко О. Н. 
|частина         =
|заголовок      = Теоретико-числові алгоритми в криптографії 
|оригінал      = 
|посилання        = http://www.ict.edu.ru/ft/002416/book.pdf
|видання       = 
|відповідальний = 
|місце         = М. 
|видавництво  = [[МЦНМО]]
|рік           = 2003 
|том           = 
|сторінки       = 
|сторінок       = 328 
|isbn          = 5-94057-103-4 
|ref           = Василенко 
}}
* ''Ю.&nbsp;П.&nbsp;Соловйов, В.&nbsp;А.&nbsp;Садовничий, Е.&nbsp;Т.&nbsp;Шавгулидзе, В.&nbsp;В.&nbsp;Бєлокуров.'' Еліптичні криві та сучасні алгоритми [[Теорія чисел|теорії чисел]]. Москва-Іжевськ: Інститут комп'ютерних досліджень, 2003.
* {{Citation 
|last=Brent 
|first=Richard P. 
|year=1980 
|title=An Improved Monte Carlo Factorization Algorithm 
|journal=BIT 
|volume=20 
|issue= 
|pages=176-184 
|url=http://wwwmaths.anu.edu.au/~brent/pd/rpb051i.pdf 
|issn= 
|doi=10.1007/BF01933190 
|ref=harv 
|accessdate=29 жовтня 2014 
|archive-date=24 вересня 2009 
|archive-url=https://web.archive.org/web/20090924082516/http://wwwmaths.anu.edu.au/~brent/pd/rpb051i.pdf 
}}
* {{стаття 
|автор    = 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 
}}
* {{книга 
|автор         = Childs, Lindsay N. 
|частина         = Congruences
|заголовок      = Введення у вищу алгебру 
|оригінал      = Concrete Introduction to Higher Algebra
|посилання        = http://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
}}
* {{книга 
|автор         = Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. 
|заголовок      = Алгоритми: побудова й аналіз 
|оригінал      = Introduction to algorithms
|посилання        = http://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
}}
* {{книга 
|автор         = Koshy T. 
|частина         = Congruences
|заголовок      = Елементарна теорія чисел та її додатки 
|оригінал      = Elementary Number Theory with Applications
|посилання        = http://books.google.ru/books?id=d5Z5I3gnFh0C
|видання       = 2 
|місце         = USA
|видавництво  = Academic Press
|рік           = 2007 
|сторінки      = 238 
|сторінок       = 771 
|isbn          = 9780123724878 
|ref           = Koshy
}}
* {{Citation
|last=Pollard
|first=J. M.
|year=1975
|title=A Monte Carlo method for factorization
|journal=BIT Numerical Mathematics
|volume=15
|issue=3
|pages=331-334
|url=http://www.cs.cmu.edu/~avrim/451f11/lectures/lect1122_Pollard.pdf
|issn=
|ref=harv
|accessdate=13 грудня 2021
|archive-date=21 січня 2022
|archive-url=https://web.archive.org/web/20220121052329/http://www.cs.cmu.edu/~avrim/451f11/lectures/lect1122_Pollard.pdf
}}
* {{статья
 |автор    = 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
|посилання        = http://books.google.ru/books?id=94DaZuVETzIC
|видання       = 2-е  
|місце         = USA
|видавництво  = Springer
|рік           = 2012 
|сторінки       = 183 
|сторінок       = 464 
|isbn          = 978-0-8176-8297-2 
|ref           = Reisel
}}

{{Алгоритми теорії чисел}}
[[Категорія:Алгоритми факторизації]]