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

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

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

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

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

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

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

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

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

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

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

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

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

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

$(x_i,x_{2i},Q_i),i=1,2,...$, де $Q_i\equiv \prod _{j=1}^i(x_{2j}-x_j)(\mathrm{m}\mathrm{o}\mathrm{d}N)$.

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

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

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

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

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

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

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

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

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

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

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

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

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

Нехай $F(x)=(x^2-1)\mathrm{m}\mathrm{o}\mathrm{d}N$. Зауважимо, що й $(x_j-x_i)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}p)$, то $(f(x_j)-f(x_i))\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}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]$Шаблон:Sfn.

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

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

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

Нехай $N=8051$, $F(x)=(x^2+1)\mathrm{m}\mathrm{o}\mathrm{d}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.

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

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

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

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

Нехай послідовність $\{u_n\}$ складається з різниць $x_i-x_j$, що перевіряються під час роботи алгоритму. Визначимо нову послідовність $\{z_n\}$, де $z_n=u_n\mathrm{m}\mathrm{o}\mathrm{d}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{m}\mathrm{o}\mathrm{d}q$, тобто, $x_i-x_j=kq$ для деякого цілого $k$. Якщо $x_i\ne x_j$, що виконується з великою ймовірністю, то шуканий дільник $q$ числа $N$ буде знайдено як $\mathrm{G}\mathrm{C}\mathrm{D}(N,|x_i-x_j|)$. Оскільки $\sqrt{q}⩽n^{1/4}$, то з імовірністю, що перевищує 0,5, дільник $N$ буде знайдено за $1.18\times N^{1/4}$ ітераційШаблон:Sfn.

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

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

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

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

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

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

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

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

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

Див. також

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

Література

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