ρ-алгоритм Полларда
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/50/Pollard_rho_cycle.svg/300px-Pollard_rho_cycle.svg.png)
ρ-алгоритм Полларда — алгоритм факторизації цілих чисел. Запропонований 1975 року Джоном Поллардом[en], ґрунтується на алгоритмі Флойда пошуку циклу в послідовності і деяких наслідках з парадоксу днів народжень. Алгоритм найбільш ефективний для факторизації складених чисел із досить малими множниками в розкладі. Складність алгоритму оцінюється як .
У всіх варіантах ρ-алгоритму Поларда будується числова послідовність, елементи якої, починаючи з деякого номера n, утворюють цикл, що можна проілюструвати розташуванням членів послідовності у вигляді грецької букви ρ. Це й послужило назвою для сімейства методів.
Історія алгоритму
Наприкінці 60-х років XX століття Дональд Кнут опублікував досить ефективний алгоритм пошуку циклу в послідовності , також відомий, як алгоритм «черепаха та заєць», який він пов'язував з ім'ям Флойда[1]. Джон Поллард[en], Дональд Кнут та інші математики проаналізували поведінку цього алгоритму в середньому випадку. Було запропоновано кілька модифікацій та поліпшень алгоритму.
У 1975 році Поллард опублікував статтю, в якій він, ґрунтуючись на алгоритмі Флойда виявлення циклів, виклав ідею алгоритму факторизації чисел, який виконується за час, пропорційний [2]. Автор назвав його методом факторизації Монте-Карло, тому, що в процесі обчислення генерується псевдовипадкова послідовність чисел. Проте пізніше метод все-таки отримав свою сучасну назву — ρ-алгоритм Поларда[3].
У 1981 році Річард Брент[ru] і Джон Полард за допомогою алгоритму знайшли найменші дільники чисел Ферма при [4].
Так, , де — просте число, що складається з 62 десяткових цифр.
У межах проекту «Cunningham project» алгоритм Полларда допоміг знайти дільник числа довжиною 19 цифр. Більші дільники також можна б знайти, але відкриття методу факторизації за допомогою еліптичних кривих[ru] зробило алгоритм Полларда неконкурентоспроможним[5].
Опис алгоритму
Оригінальна версія
Розглянемо послідовність цілих чисел , таку що та , де — число, яке потрібно факторизувати. Оригінальний алгоритм виглядає таким чином[6].
- 1. Будемо обчислювати трійки чисел
- , де .
- Причому кожна така трійка отримується з попередньої.
- 2. Щоразу, коли число кратне числу (скажімо, ), будемо обчислювати найбільший спільний дільник будь-яким відомим методом.
- 3. Якщо , то знайдено часткове розкладання числа , причому .
- Знайдений дільник може бути складовим, тому його також необхідно факторизувати. Якщо число складене, то продовжуємо алгоритм з модулем .
- 4. Обчислення повторюються раз. Наприклад, можна зупинити алгоритм при . Якщо при цьому число не було до кінця факторизовано, можна вибрати, наприклад, інше початкове число .
Сучасна версія
Нехай складене ціле додатне число, яке потрібно розкласти на множники. Алгоритм виглядає таким чином:[7]
- Вибираємо невелике число та будуємо послідовність , визначаючи кожне наступне як .
- Одночасно на кожному i-ому кроці обчислюємо для будь-яких , таких, що , наприклад, .
- Якщо виявили, що , то обчислення закінчується, і знайдене на попередньому кроці число є дільником . Якщо не є простим числом, то процедуру пошуку дільників можна продовжити, узявши як число .
Як на практиці обирати функцію ? Функція має бути не надто складною для обчислення, але в той же час не має бути лінійним многочленом, а також не повинна породжувати взаємно однозначне відображення. Зазвичай за беруть функцію або [8]. Однак не слід застосовувати функції та [6].
Якщо відомо, що для дільника числа справедливо при деякому , то має сенс застосувати [6].
Істотним недоліком алгоритму в такий реалізації є необхідність зберігати велику кількість попередніх значень .
Покращення алгоритму
Початкова версія алгоритму має низку недоліків. На даний момент[коли?] існує кілька підходів до поліпшення оригінального методу.
Нехай . Зауважимо, що й , то , тому, якщо пара дає нам розв'язок, то розв'язок дасть будь-яка пара .
Тому, немає потреби перевіряти всі пари , а можна обмежитися парами виду , де , і пробігає набір послідовних значень 1, 2, 3,…, а набуває значення з інтервалу . Наприклад, , , а [9].
Цю ідею запропонував Річард Брент[ru] у 1980 році[10] і вона дозволяє зменшити кількість виконуваних операцій приблизно на чверть (25%)[11].
Ще одну варіацію ρ-методу Поларда розробив Флойд. За Флойдом, значення оновлюється на кожному кроці за формулою , тому на кроці i будуть отримані значення , , і НСД на цьому кроці обчислюється для та [7].
Приклад факторизації числа
Нехай , , , .
i | xi | yi | НСД (|xi −yi|, 8051) |
---|---|---|---|
1 | 5 | 26 | 1 |
2 | 26 | 7474 | 1 |
3 | 677 | 871 | 97 |
Таким чином, 97 — нетривіальний дільник числа 8051. Використовуючи інші варіанти поліному , можна також отримати дільник 83.
Обґрунтування ρ-методу Поларда
Алгоритм ґрунтується на відомому парадоксі днів народження.
Теорема (Парадокс днів народження)
|
Слід зазначити, що ймовірність в парадоксі днів народження досягається при .
Нехай послідовність складається з різниць , що перевіряються під час роботи алгоритму. Визначимо нову послідовність , де , — менший з дільників числа .
Усі члени послідовності менші . Якщо розглядати її як випадкову послідовність цілих чисел, менших , то, згідно з парадоксом днів народження, імовірність того, що серед її членів трапляться два однакових, перевищить при , тоді має бути не менше .
Якщо , тоді , тобто, для деякого цілого . Якщо , що виконується з великою ймовірністю, то шуканий дільник числа буде знайдено як . Оскільки , то з імовірністю, що перевищує 0,5, дільник буде знайдено за ітерацій[7].
Складність алгоритму
Щоб оцінити складність алгоритму, можна розглядати послідовність, що будується в процесі обчислень, як випадкову (звісно, ні про яку строгість при цьому говорити не можна). Щоб повністю факторизувати число довжиною біт, достатньо знайти всі його дільники, які не переважають , що вимагає максимум порядку арифметичних операцій, або бітових операцій.
Тому складність алгоритму оцінюється, як [12]. Однак у цій оцінці не враховуються накладні витрати з обчислення найбільшого спільного дільника. Отримана складність алгоритму, хоча і не є точною, проте достатньо добре узгоджується з практикою.
Виконується така теорема. Нехай — складене число. Тоді існує така стала , що для будь-якого додатного числа ймовірність події, що полягає в тому, що ρ-метод Поларда не знайде нетривіального дільника за час , не перевершує величини . Ця теорема випливає з парадоксу днів народження.
Особливості реалізації
Обсяг пам'яті, використовуваний алгоритмом, можна значно зменшити.
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)); }
у цьому варіанті обчислення потребує зберігати в пам'яті всього три змінні , , і , що вигідно відрізняє метод в такій реалізації від інших методів факторизації чисел[7].
Розпаралелювання алгоритму
Алгоритм Полларда дозволяє розпаралелювання з використанням будь-якого стандарту паралельних обчислень (наприклад, OpenMP та ін.).
Існує декілька варіантів розпаралелювання, але їх спільна ідея полягає в тому, що кожний процесор виконує послідовний алгоритм, причому початкове число та/або поліном мають бути різними для кожного процесора. Очікується, що на якомусь процесорі початкові параметри (випадково) виявляться більш вдалими і дільник буде знайдено швидше, однак цей випадок недетермінований (імовірнісний). Прискорення від такої паралельної реалізації значно менше лінійного.
Припустимо, що є однакових процесорів. Якщо ми використовуємо різних послідовностей (тобто, різних поліномів ), то ймовірність того, що перші чисел в цих послідовностях будуть різними за модулем приблизно дорівнює . Таким чином, прискорення можна оцінити як [5]. Тобто, збільшення швидкості вдвічі можна очікувати, якщо процесорів буде вчетверо більше.
Річард Крандалл припустив, що можна досягти прискорення , однак на 2000-й рік це твердження не було перевірено[13].
Див. також
- P-1 алгоритм Поларда[ru]
- P-спосіб Поларда дискретного логарифмування[ru]
- P+1 метод Вільямса[ru]
- Спосіб пробних поділів[ru]
- Спосіб Ферма
- Факторизація за допомогою еліптичних кривих[ru]
- Метод решета числового поля
Примітки
- ↑ Перший опис алгоритму «черепахи та зайця» з'явився в другому томі Мистецтва програмування Дональда Кнута (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 (PDF), BIT, 20: 176—184, doi:10.1007/BF01933190
- Brent R.P. Деякі Паралельні алгоритми факторизації чисел. — 1999. — С. 7. — DOI: .
- 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
- 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.