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

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

ρ-алгоритм Джона Поларда[en], запропонований ним в 1975 році, служить для факторизації цілих чисел. Він ґрунтується на алгоритмі Флойда пошуку довжини циклу в послідовності[en] і деяких наслідках з парадоксу днів народжень. Алгоритм найбільш ефективний при факторизації складених чисел з досить малими множниками в розкладанні. Складність алгоритму оцінюється як .

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

Історія алгоритму[ред. | ред. код]

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

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

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

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

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

Опис алгоритму[ред. | ред. код]

Оригінальна версія[ред. | ред. код]

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

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

Сучасна версія[ред. | ред. код]

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

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

Як на практиці вибирати функцію ? Функція повинна бути не надто складною для обчислення, але в той же час не повинна бути лінійним многочленом, а також не повинна породжувати взаємно однозначне відображення. Зазвичай за беруть функцію або [8]. Однак не слід використовувати функції та [6].

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

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

Покращення алгоритму[ред. | ред. код]

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

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

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

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

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

Приклад факторизації числа[ред. | ред. код]

Нехай , , , .

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

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

Обґрунтування P-методу Поларда[ред. | ред. код]

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

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

Нехай . Для випадкової вибірки з елементів, кожний з яких менший від , де , ймовірність того, що два елементи виявляться однаковими .

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

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

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

Якщо , тоді , тобто, для деякого цілого . Якщо , що виконується з великою ймовірністю, то шуканий дільник числа буде знайдено як . Оскільки , то з ймовірністю, що перевищує 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].

Річард Крандалл припустив, що досяжне прискорення , однак дане твердження поки не перевірено[13].

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

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

Література[ред. | ред. код]