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

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

Історія алгоритму Наприкінці 60-х років XX століття Дональд Кнут опублікував досить ефективний алгоритм пошуку циклу в послідовності, також відомий, як алгоритм «черепаха та заєць», який він пов'язував з ім'ям ФлойдаПерший опис алгоритму «черепахи та зайця» з'явився в другому томі Мистецтва програмування Дональда Кнута (), у вправах 6 та 7 (стор. 7). На сторінці 4 Кнут приписує цей алгоритм Флойду, не посилаючись на джерела. Хоча Флойд і опублікував 1967 року статтю: , однак у ній він описав алгоритми пошуку простих циклів в орієнтованому графі.. , Дональд Кнут та інші математики проаналізували поведінку цього алгоритму в середньому випадку. Було запропоновано кілька модифікацій та поліпшень алгоритму.

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

У 1981 році і Джон Поллард за допомогою цього алгоритму знайшли менший дільник восьмого числа Ферма .

Так, , де — просте число, що складається з 62 десяткових цифр.

У межах проекту «» алгоритм Полларда допоміг знайти дільник числа довжиною 19 цифр. Більші дільники також можна б знайти, але відкриття зробило алгоритм Полларда неконкурентоспроможним.

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

Оригінальна версія Розглянемо послідовність цілих чисел , таку що та , де  — число, яке потрібно факторизувати. Оригінальний алгоритм виглядає таким чином.

1. Будемо обчислювати трійки чисел , де . Причому кожна така трійка отримується з попередньої. 2. Щоразу, коли число кратне числу (скажімо, ), будемо обчислювати найбільший спільний дільник будь-яким відомим методом. 3. Якщо , то знайдено часткове розкладання числа , причому . Знайдений дільник може бути складовим, тому його також необхідно факторизувати. Якщо число складене, то продовжуємо алгоритм з модулем . 4. Обчислення повторюються раз. Наприклад, можна зупинити алгоритм при . Якщо при цьому число не було до кінця факторизовано, можна вибрати, наприклад, інше початкове число .

Сучасна версія Нехай складене ціле додатне число, яке потрібно розкласти на множники. Алгоритм виглядає таким чином: Вибираємо невелике число та будуємо послідовність , визначаючи кожне наступне як . Одночасно на кожному i-ому кроці обчислюємо для будь-яких , таких, що , наприклад, . Якщо виявили, що , то обчислення закінчується, і знайдене на попередньому кроці число є дільником . Якщо не є простим числом, то процедуру пошуку дільників можна продовжити, узявши як число .

Як на практиці обирати функцію ? Функція має бути не надто складною для обчислення, але в той же час не має бути лінійним многочленом, а також не повинна породжувати взаємно однозначне відображення. Зазвичай за беруть функцію або Н. Ю. Золотих. Лекції по комп'ютерній алгебрі. Лекция 11. ρ-метод Полларда. . Однак не слід застосовувати функції та .

Якщо відомо, що для дільника числа справедливо при деякому , то має сенс застосувати .

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

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

Нехай . Зауважимо, що й , то , тому, якщо пара дає нам розв'язок, то розв'язок дасть будь-яка пара .

Тому, немає потреби перевіряти всі пари , а можна обмежитися парами виду , де , і пробігає набір послідовних значень 1, 2, 3,…, а набуває значення з інтервалу . Наприклад, , , а .

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

Ще одну варіацію ρ-методу Поларда розробив Флойд. За Флойдом, значення оновлюється на кожному кроці за формулою , тому на кроці i будуть отримані значення , , і НСД на цьому кроці обчислюється для та .

Приклад факторизації числа Нехай , , , .

ixiyiНСД (|xi −yi|, 8051)1526122674741367787197

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

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

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

Слід зазначити, що ймовірність в парадоксі днів народження досягається при .

Нехай послідовність складається з різниць , що перевіряються під час роботи алгоритму. Визначимо нову послідовність , де ,  — менший з дільників числа .

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

Якщо , тоді , тобто, для деякого цілого . Якщо , що виконується з великою ймовірністю, то шуканий дільник числа буде знайдено як . Оскільки , то з імовірністю, що перевищує 0,5, дільник буде знайдено за ітерацій.

Складність алгоритму Щоб оцінити складність алгоритму, можна розглядати послідовність, що будується в процесі обчислень, як випадкову (звісно, ні про яку строгість при цьому говорити не можна). Щоб повністю факторизувати число довжиною біт, достатньо знайти всі його дільники, які не переважають , що вимагає максимум порядку арифметичних операцій, або бітових операцій.

Тому складність алгоритму оцінюється, як . Однак у цій оцінці не враховуються накладні витрати з обчислення найбільшого спільного дільника. Отримана складність алгоритму, хоча і не є точною, проте достатньо добре узгоджується з практикою.

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

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

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

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

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

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

Припустимо, що є однакових процесорів. Якщо ми використовуємо різних послідовностей (тобто, різних поліномів ), то ймовірність того, що перші чисел в цих послідовностях будуть різними за модулем приблизно дорівнює . Таким чином, прискорення можна оцінити як . Тобто, збільшення швидкості вдвічі можна очікувати, якщо процесорів буде вчетверо більше.

Річард Крандалл припустив, що можна досягти прискорення , однак на 2000-й рік це твердження не було перевірено.

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

Примітки

Література

Ю. П. Соловйов, В. А. Садовничий, Е. Т. Шавгулидзе, В. В. Бєлокуров. Еліптичні криві та сучасні алгоритми теорії чисел. Москва-Іжевськ: Інститут комп'ютерних досліджень, 2003.