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

Числова послідовність зациклюється, починаючи з деякого n. Цикл виглядає як грецька літера ρ.

ρ-алгоритм Полларда — алгоритм факторизації цілих чисел, що ґрунтується на пошуку циклу в послідовності і деяких наслідках із парадоксу днів народжень. Його запропонував Джон Поллард (1975). Алгоритм найбільш ефективний для факторизації складених чисел із досить малими множниками в розкладі. Обчислювальна складність оцінюється як $O(N^{1/4})$.

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

Історія алгоритму

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

У 1975 році Поллард опублікував статтю, в якій він, ґрунтуючись на алгоритмі Флойда виявлення циклів, виклав ідею алгоритму факторизації чисел, який виконується за час, пропорційний $N^{1/4}$. Автор назвав його методом факторизації Монте-Карло, тому, що в процесі обчислення генерується псевдовипадкова послідовність чисел. Проте пізніше метод все-таки назвали ρ-алгоритмом Полларда.

У 1981 році Річард Брент і Джон Поллард за допомогою цього алгоритму знайшли менший дільник восьмого числа Ферма $F_{8}=2^{2^{8}}+1$.

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

У межах проекту «Cunningham project» алгоритм Полларда допоміг знайти дільник числа $2^{2386}+1$ довжиною 19 цифр. Більші дільники також можна б знайти, але відкриття методу факторизації за допомогою еліптичних кривих зробило алгоритм Полларда неконкурентоспроможним.

Опис алгоритму

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

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

1. Будемо обчислювати трійки чисел

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

Причому кожна така трійка отримується з попередньої.

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

3. Якщо $1<d_{i}<N$, то знайдено часткове розкладання числа $N$, причому $N=d_{i}\times (N/d_{i})$.

Знайдений дільник $d_{i}$ може бути складовим, тому його також необхідно факторизувати. Якщо число $N/d_{i}$ складене, то продовжуємо алгоритм з модулем $N'=N/d_{i}$.

4. Обчислення повторюються $S$ раз. Наприклад, можна зупинити алгоритм при $i=S=10^{5}$. Якщо при цьому число не було до кінця факторизовано, можна вибрати, наприклад, інше початкове число $x_{0}$.

Сучасна версія

Нехай $N$ складене ціле додатне число, яке потрібно розкласти на множники. Алгоритм виглядає таким чином:

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

Як на практиці обирати функцію $F(x)$? Функція має бути не надто складною для обчислення, але в той же час не має бути лінійним многочленом, а також не повинна породжувати взаємно однозначне відображення. Зазвичай за $F(x)$ беруть функцію $F(x)=x^{2}\pm 1(\mathrm {mod} \,N)$ або $F(x)=x^{2}\pm a(\mathrm {mod} \,N)$. Однак не слід застосовувати функції $x^{2}-2$ та $x^{2}$.

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

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

Покращення алгоритму

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

Нехай $F(x)=(x^{2}-1)\mathrm {mod} \,N$. Зауважимо, що й $(x_{j}-x_{i})\equiv 0(\mathrm {mod} \,p)$, то $(f(x_{j})-f(x_{i}))\equiv 0(\mathrm {mod} \,p)$, тому, якщо пара $(x_{i},x_{j})$ дає нам розв'язок, то розв'язок дасть будь-яка пара $(x_{i+k},x_{j+k})$.

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

Цю ідею запропонував Річард Брент у 1980 році і вона дозволяє зменшити кількість виконуваних операцій приблизно на чверть (25%).

Ще одну варіацію ρ-методу Поларда розробив Флойд. За Флойдом, значення $y$ оновлюється на кожному кроці за формулою $y=F^{2}(y)=F(F(y))$, тому на кроці i будуть отримані значення $x_{i}=F^{i}(x_{0})$, $y_{i}=x_{2i}=F^{2i}(x_{0})$, і НСД на цьому кроці обчислюється для $N$ та $y-x$.

Приклад факторизації числа

Нехай $N=8051$, $F(x)=(x^{2}+1)\,\mathrm {mod} \,8051$, $x_{0}=y_{0}=2$, $y_{i+1}=F(F(y_{i}))$.

i	xi	yi	НСД (|xi −yi|, 8051)
1	5	26	1
2	26	7474	1
3	677	871	97

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

Обґрунтування ρ-методу Полларда

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

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

Нехай $\lambda >0$. Для випадкової вибірки з $l+1$ елементів, кожний з яких менший від $q$, де $l={\sqrt {2\lambda q}}$, ймовірність того, що два елементи виявляться однаковими $p>1-\exp ^{-\lambda }$.

Слід зазначити, що ймовірність $p=0.5$ в парадоксі днів народження досягається при $\lambda \approx 0.69$.

Нехай послідовність $\{u_{n}\}$ складається з різниць $x_{i}-x_{j}$, що перевіряються під час роботи алгоритму. Визначимо нову послідовність $\{z_{n}\}$, де $z_{n}=u_{n}\,\mathrm {mod} \,q$, $q$ — менший з дільників числа $N$.

Усі члени послідовності $\{z_{n}\}$ менші ${\sqrt {N}}$. Якщо розглядати її як випадкову послідовність цілих чисел, менших $q$, то, згідно з парадоксом днів народження, імовірність того, що серед $l+1$ її членів трапляться два однакових, перевищить $1/2$ при $\lambda \approx 0.69$, тоді $l$ має бути не менше ${\sqrt {2\lambda q}}\approx {\sqrt {1.4q}}\approx 1.18{\sqrt {q}}$.

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

Складність алгоритму

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

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

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

у цьому варіанті обчислення потребує зберігати в пам'яті всього три змінні $N$, $x$, і $y$, що вигідно відрізняє метод в такій реалізації від інших методів факторизації чисел.

Розпаралелювання алгоритму

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

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

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

Річард Крандалл припустив, що можна досягти прискорення $O(P/(\log {P})^{2})$, однак на 2000-й рік це твердження не було перевірено.

Див. також

• Метод Монте-Карло

Література

• Ішмухаметов Ш. Т. Методи факторизації натуральних чисел: Навчальний посібник. — Казань : Казанський Університет, 2011. — С. 61-64.
• Василенко О. Н. Теоретико-числові алгоритми в криптографії. — М. : МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4.
• Ю. П. Соловйов, В. А. Садовничий, Е. Т. Шавгулидзе, В. В. Бєлокуров. Еліптичні криві та сучасні алгоритми теорії чисел. Москва-Іжевськ: Інститут комп'ютерних досліджень, 2003.
• Brent, Richard P. (1980), An Improved Monte Carlo Factorization Algorithm (PDF), BIT, 20: 176—184, doi:10.1007/BF01933190, архів оригіналу (PDF) за 24 вересня 2009, процитовано 29 жовтня 2014
• Brent R.P. Деякі Паралельні алгоритми факторизації чисел. — 1999. — С. 7. — DOI:10.1017/S0305004100049252.
• Childs, Lindsay N. Congruences // Введення у вищу алгебру = Concrete Introduction to Higher Algebra. — 3. — USA : Springer, 2009. — С. 471-473. — ISBN 978-0-387-74725-5.
• Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Алгоритми: побудова й аналіз = Introduction to algorithms. — 2. — USA : MIT Press, 2001. — С. 897-907. — ISBN 9780262032933.
• Crandall R.E. Розпаралелювання P-алгоритму факторизації Поларда. — 1999.
• Koshy T. Congruences // Елементарна теорія чисел та її додатки = Elementary Number Theory with Applications. — 2. — USA : Academic Press, 2007. — С. 238. — ISBN 9780123724878.
• Pollard, J. M. (1975), A Monte Carlo method for factorization (PDF), BIT Numerical Mathematics, 15 (3): 331—334, архів оригіналу (PDF) за 21 січня 2022, процитовано 13 грудня 2021
• 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. — ISBN 978-0-8176-8297-2.