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

(перенаправлено с «Ρ-алгоритм Полларда»)

Ро-алгоритм (-алгоритм) — предложенный Джоном Поллардом[англ.] в 1975 году алгоритм, служащий для факторизации (разложения на множители) целых чисел. Данный алгоритм основывается на алгоритме Флойда поиска длины цикла в последовательности и некоторых следствиях из парадокса дней рождения. Алгоритм наиболее эффективен при факторизации составных чисел с достаточно малыми множителями в разложении. Сложность алгоритма оценивается как [1].

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

ρ-алгоритм Полларда строит числовую последовательность, элементы которой образуют цикл, начиная с некоторого номера n, что может быть проиллюстрировано, расположением чисел в виде греческой буквы ρ, что послужило названием семейству алгоритмов[2][3].

История алгоритма

править

В конце 60-х годов XX века Роберт Флойд придумал достаточно эффективный метод решения задачи нахождения цикла, также известный, как алгоритм «черепаха и заяц»[4]. Джон Поллард, Дональд Кнут и другие математики проанализировали поведение этого алгоритма в среднем случае. Было предложено несколько модификаций и улучшений алгоритма[5].

В 1975 году Поллард опубликовал статью[6], в которой он, основываясь на алгоритме Флойда обнаружения циклов, изложил идею алгоритма факторизации чисел, работающего за время, пропорциональное  [6][1]. Автор алгоритма назвал его методом факторизации Монте-Карло, отражая кажущуюся случайность чисел, генерируемых в процессе вычисления. Однако позже метод всё-таки получил своё современное название — ρ-aлгоритм Полларда[7].

В 1981 году Ричард Брент и Джон Поллард с помощью алгоритма нашли наименьшие делители чисел Ферма   при  [8]. Скорость алгоритма сильно зависит лишь от величины наименьшего делителя исходного числа, но не от самого числа. Так, поиск наименьшего делителя седьмого числа Ферма —  , занимает гораздо больше времени, чем поиск делителя двенадцатого числа Ферма (т.к. его делитель 114689 значительно меньше, хотя само число состоит более чем из 1200 десятичных цифр).

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

Описание алгоритма

править

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

править

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

1. Вычисляются тройки чисел
 , где  .
Причём каждая такая тройка получается из предыдущей.
2. Каждый раз, когда число   кратно числу   (скажем,  ), вычисляется наибольший общий делитель   любым известным методом.
3. Если  , то частичное разложение числа   найдено, причём  .
Найденный делитель   может быть составным, поэтому его также необходимо факторизовать. Если число   составное, то продолжаем алгоритм с модулем  .
4. Вычисления повторяются   раз. Если при этом число не было до конца факторизовано, выбирается, например, другое начальное число  .

Современная версия

править

Пусть   составное целое положительное число, которое требуется разложить на множители. Алгоритм выглядит следующим образом[11]:

  1. Случайным образом выбирается небольшое число  [12] и строится последовательность  , определяя каждое следующее как  .
  2. Одновременно на каждом i-ом шаге вычисляется   для каких-либо  ,   таких, что  , например,  .
  3. Если  , то вычисление заканчивается, и найденное на предыдущем шаге число   является делителем  . Если   не является простым числом, то процедуру поиска делителей продолжается, взяв в качестве   число  .

На практике функция   выбирается не слишком сложной для вычисления (но в то же время не линейным многочленом), при условии того, что она не должна порождать взаимно однозначное отображение. Обычно в качестве   выбираются функции  [12] или  [13]. Однако функции   и   не подходят[10].

Если известно, что для делителя   числа   справедливо   при некотором  , то имеет смысл использовать  [10].

Существенным недостатком алгоритма в такой реализации является необходимость хранить большое число предыдущих значений  .

Улучшения алгоритма

править

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

Пусть  . Тогда, если  , то  , поэтому, если пара   даёт решение, то решение даст любая пара  .

Поэтому нет необходимости проверять все пары  , а можно ограничиться парами вида  , где  , и   пробегает набор последовательных значений 1, 2, 3, …, а   принимает значения из интервала  . Например,  ,  , а  [11].

Эта идея была предложена Ричардом Брентом в 1980 году[14] и позволяет уменьшить количество выполняемых операций приблизительно на 25 %[15].

Ещё одна вариация ρ-алгоритма Полларда была разработана Флойдом. Согласно Флойду, значение   обновляется на каждом шаге по формуле  , поэтому на шаге   будут получены значения  ,  , и НОД на этом шаге вычисляется для   и  [11].

Пример факторизации числа

править

Данный пример наглядно демонстрирует ρ-алгоритм факторизации (версия алгоритма, с улучшением Флойда), для числа N = 8051:

Таблица: факторизация числа 8051
n = 8051, F(x) = (x2 + 1) mod n , x0 = y0 = 2
i xi=F(xi-1) yi=F(F(yi-1)) НОД(|xiyi|, 8051)
1 5 26 1
2 26 7474 1
3 677 871 97

Используя другие варианты полинома  , можно также получить делитель 83:

Таблица: факторизация числа 8051
n = 8051, F(x) = (x2 + 3) mod n , x0 = y0 = 2
i xi=F(xi-1) yi=F(F(yi-1)) НОД(|xiyi|, 8051)
1 7 52 1
2 52 1442 1
3 2707 778 1
4 1442 3932 83

Таким образом, d1 = 97, d2 = 83 — нетривиальные делители числа 8051.

После нахождения делителя числа, в ρ-алгоритме предлагается продолжать вычисления и искать делители числа  , если   не является простым. В этом простом примере данного шага совершать не потребовалось[11].

Обоснование ρ-алгоритма Полларда

править

Алгоритм основывается на известном парадоксе дней рождения.

Парадокс дней рождений, кратко:
Пусть  . Для случайной выборки из   элементов, каждый из которых меньше  , где  , вероятность того, что два элемента окажутся одинаковыми  .

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

Пусть последовательность   состоит из разностей  , проверяемых в ходе работы алгоритма. Определяется новая последовательность  , где  ,   — меньший из делителей числа  .

Все члены последовательности   меньше  . Если рассматривать её как случайную последовательность целых чисел, меньших  , то, согласно парадоксу дней рождения, вероятность того, что среди   её членов попадутся два одинаковых, превысит   при  , тогда   должно быть не меньше  .

Если  , тогда  , то есть,   для некоторого целого  . Если  , что выполняется с большой вероятностью, то искомый делитель   числа   будет найден как  . Поскольку  , то с вероятностью, превышающей   , делитель   будет найден за   итераций[11].

Сложность алгоритма

править

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

Поэтому сложность алгоритма оценивается, как  [16]. Однако в этой оценке не учитываются накладные расходы по вычислению наибольшего общего делителя. Полученная сложность алгоритма, хотя и не является точной, достаточно хорошо согласуется с практикой.

Справедливо следующее утверждение: пусть   — составное число. Тогда существует такая константа  , что для любого положительного числа   вероятность события, состоящего в том, что ρ-алгоритм Полларда не найдет нетривиального делителя   за время  , не превосходит величины  . Данное утверждение следует из парадокса дней рождения[17].

Особенности реализации

править

Объём памяти, используемый алгоритмом, можно значительно уменьшить.

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

В этом варианте вычисление требует хранить в памяти всего три переменные  ,  , и  , что выгодно отличает алгоритм в такой реализации от других методов факторизации чисел[11].

Распараллеливание алгоритма

править

Алгоритм Полларда допускает распараллеливание с использованием как систем с разделяемой памятью, так и систем с распределенной памятью (передача сообщений), однако второй случай является наиболее интересным с практической точки зрения[18].

Система с распределенной памятью

править

Существующий метод распараллеливания заключается в том, что каждый вычислительный узел исполняет один и тот же последовательный алгоритм, однако, исходное число   и/или полином   берутся различными. Для упрощения распараллеливания, предлагается получать их из генератора случайных чисел. Однако такая параллельная реализация не даёт линейного ускорения[19].

Предположим что есть   одинаковых исполнителей. Если мы используем   различных последовательностей (то есть различных полиномов  ), то вероятность того, что первые   чисел в этих последовательностях будут различными по модулю  , будет примерно равна  . Таким образом, максимальное ускорение можно оценить как  [9].

Ричард Крэндалл предположил, что достижимо ускорение  , однако данное утверждение пока не проверено[20].

Система с общей памятью

править

Предыдущий метод, очевидно, можно использовать и на системах с общей памятью, однако, гораздо разумнее использовать единый генератор  [21].

Примечания

править
  1. 1 2 Pollard, 1974, с. 521–528.
  2. Christensen, 2009, 3.3.3.0.
  3. Chatterjee, 2008, 5.2.2.
  4. Floyd, 1967, с. 636–644.
  5. Brent, 1980, An improved Monte Carlo factorization algorithm, с. 176.
  6. 1 2 3 Pollard, 1975, A Monte Carlo method for factorization, с. 176.
  7. Koshy, 2007, Elementary Number Theory with Applications.
  8. Childs, 2009, A Concrete Introduction to Higher Algebra.
  9. 1 2 Brent, 1999, Some parallel algorithms for integer factorization..
  10. 1 2 3 Pollard, 1975, A Monte Carlo method for factorization.
  11. 1 2 3 4 5 6 Ишмухаметов, 2011, с. 64.
  12. 1 2 Mollin, 2006, с. 215—216.
  13. Золотых Н. Ю. Лекции по компьютерной алгебре. Лекция 11. ρ-метод Полларда. Архивная копия от 30 октября 2014 на Wayback Machine
  14. Brent, 1980, An improved Monte Carlo factorization algorithm, с. 176—184.
  15. Reisel, 2012, Selected Areas in Cryptography. Prime Numbers and Computer Methods for Factorization. 2nd ed..
  16. Cormen, 2001, Introduction to Algorithms. Section 31.9. Integer Factorization. Pollard's rho heuristic..
  17. Ишмухаметов, 2011, с. 63.
  18. Косяков, 2014, с. 12.
  19. Kuhn, 2001, Random Walks Revisited: Extensions of Pollard’s Rho Algorithm for Computing Multiple Discrete Logarithms, с. 212—229.
  20. Crandall, 1999, Parallelization of Polldar-rho factorization.
  21. Косяков, 2014, с. 19.

Литература

править