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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вибираємо невелике число $x_{0}$ та будуємо послідовність $\{x_{n}\},n=0,1,2,...$ , визначаючи кожне наступне як $x_{n+1}=F(x_{n})\,(\mathrm {mod} \,\,N)$ .
Одночасно на кожному i-ому кроці обчислюємо $d=\mathrm {GCD} (N,|x_{i}-x_{j}|)$ для будь-яких $i$ , $j$ таких, що $j<i$ , наприклад, $i=2j$ .
Якщо виявили, що $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)$ [8]. Однак не слід застосовувати функції $x^{2}-2$ та $x^{2}$ [6].

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

Істотним недоліком алгоритму в такий реалізації є необхідність зберігати велику кількість попередніх значень $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]$ [9].

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

Ще одну варіацію ρ-методу Поларда розробив Флойд. За Флойдом, значення $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$ [7].

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

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

i	x_i	y_i	НСД (\|x_i −y_i\|, 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}$ ітерацій[7].

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

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

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

Виконується така теорема. Нехай $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$ , що вигідно відрізняє метод в такій реалізації від інших методів факторизації чисел[7].

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

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

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

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

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

Див. також

P-1 алгоритм Поларда
P-спосіб Поларда дискретного логарифмування
P+1 метод Вільямса
Спосіб пробних поділів
Спосіб Ферма
Факторизація за допомогою еліптичних кривих
Метод решета числового поля

Примітки

Перший опис алгоритму «черепахи та зайця» з'явився в другому томі Мистецтва програмування Дональда Кнута (Knuth, Donald E. (1969). The Art of Computer Programming, vol. II: Seminumerical Algorithms. Addison-Wesley.), у вправах 6 та 7 (стор. 7). На сторінці 4 Кнут приписує цей алгоритм Флойду, не посилаючись на джерела. Хоча Флойд і опублікував 1967 року статтю: Floyd, R.W. (1967). Non-deterministic Algorithms. J. ACM 14 (4): 636–644. doi:10.1145/321420.321422., однак у ній він описав алгоритми пошуку простих циклів в орієнтованому графі.
Brent, 1980, An Improved Monte Carlo Factorization Algorithm.
Koshy, 2007, Elementary Number Theory with Applications.
Childs, 2009, A Concrete Introduction to Higher Algebra.
Brent, 1999, Some parallel algorithms for integer factorization..
Pollard, 1975, A Monte Carlo method for factorization.
Ішмухаметов, 2011, с. 64.
Н. Ю. Золотих. Лекції по комп'ютерній алгебрі. Лекция 11. ρ-метод Полларда.
Ішмухаметов, 2011, Методи факторизації натуральних чисел: Навчальний посібник.
Brent, 1980, с. 176-184.
Reisel, 2012, Selected Areas in Cryptography. Prime Numbers and Computer Methods for Factorization. 2nd ed..
Cormen, 2001, с. 976, Introduction to Algorithms. Section 31.9. Integer Factorization. Pollard's rho heuristic..
Crandall, 1999, Parallelization of Polldar-rho factorization.

Література

Ішмухаметов Ш. Т. Методи факторизації натуральних чисел: Навчальний посібник. — Казань : Казанський Університет, 2011. — С. 61-64.
Василенко О. Н. Теоретико-числові алгоритми в криптографії. — М. : МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4.
Ю. П. Соловйов, В. А. Садовничий, Е. Т. Шавгулидзе, В. В. Бєлокуров. Еліптичні криві та сучасні алгоритми теорії чисел. Москва-Іжевськ: Інститут комп'ютерних досліджень, 2003.
Brent, Richard P. (1980). An Improved Monte Carlo Factorization Algorithm. BIT 20: 176–184. doi:10.1007/BF01933190.
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. BIT Numerical Mathematics 15 (3): 331–334.
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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Перший опис алгоритму «черепахи та зайця» з'явився в другому томі Мистецтва програмування Дональда Кнута (Knuth, Donald E. (1969). The Art of Computer Programming, vol. II: Seminumerical Algorithms. Addison-Wesley.), у вправах 6 та 7 (стор. 7). На сторінці 4 Кнут приписує цей алгоритм Флойду, не посилаючись на джерела. Хоча Флойд і опублікував 1967 року статтю: Floyd, R.W. (1967). Non-deterministic Algorithms. J. ACM 14 (4): 636–644. doi:10.1145/321420.321422., однак у ній він описав алгоритми пошуку простих циклів в орієнтованому графі.

[FOOTNOTEBrent1980An_Improved_Monte_Carlo_Factorization_Algorithm-2] Brent, 1980, An Improved Monte Carlo Factorization Algorithm.

[FOOTNOTEKoshy2007Elementary_Number_Theory_with_Applications-3] Koshy, 2007, Elementary Number Theory with Applications.

[FOOTNOTEChilds2009A_Concrete_Introduction_to_Higher_Algebra-4] Childs, 2009, A Concrete Introduction to Higher Algebra.

[FOOTNOTEBrent1999Some_parallel_algorithms_for_integer_factorization.-5] Brent, 1999, Some parallel algorithms for integer factorization..

[FOOTNOTEPollard1975A_Monte_Carlo_method_for_factorization-6] Pollard, 1975, A Monte Carlo method for factorization.

[FOOTNOTEІшмухаметов201164-7] Ішмухаметов, 2011, с. 64.

[Zolotykh-rho-pollard-8] Н. Ю. Золотих. Лекції по комп'ютерній алгебрі. Лекция 11. ρ-метод Полларда.

[FOOTNOTEІшмухаметов2011Методи_факторизації_натуральних_чисел:_Навчальний_посібник-9] Ішмухаметов, 2011, Методи факторизації натуральних чисел: Навчальний посібник.

[FOOTNOTEBrent1980176-184-10] Brent, 1980, с. 176-184.

[FOOTNOTEReisel2012Selected_Areas_in_Cryptography._Prime_Numbers_and_Computer_Methods_for_Factorization._2nd_ed.-11] Reisel, 2012, Selected Areas in Cryptography. Prime Numbers and Computer Methods for Factorization. 2nd ed..

[FOOTNOTECormen2001976Introduction_to_Algorithms._Section_31.9._Integer_Factorization._Pollard's_rho_heuristic.-12] Cormen, 2001, с. 976, Introduction to Algorithms. Section 31.9. Integer Factorization. Pollard's rho heuristic..

[FOOTNOTECrandall1999Parallelization_of_Polldar-rho_factorization-13] Crandall, 1999, Parallelization of Polldar-rho factorization.