Эта статья входит в число добротных статей

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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Ρ-алгоритм Полларда»)
Перейти к: навигация, поиск
Числовая последовательность зацикливается, начиная с некоторого n. Цикл может быть представлен в виде греческой буквы ρ.

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

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

История алгоритма[править | править вики-текст]

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

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

В 1981 году Ричард Брент и Джон Поллард с помощью алгоритма нашли наименьшие делители чисел Ферма F_{n} = 2^{2^n}+1 при 5 \leq n \leq 13[8].

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

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

Описание алгоритма[править | править вики-текст]

Оригинальная версия[править | править вики-текст]

Рассматривается последовательность целых чисел {x_{n}}, такая что x_{0}=2 и x_{i+1}=(x_{i}^{2}-1\,) (\mathrm{mod}\, N), где N — число, которое нужно факторизовать. Оригинальный алгоритм выглядит следующим образом[10][6]:

1. Вычисляются тройки чисел
(x_{i}, x_{2i}, Q_{i}), i=1,2,..., где Q_{i} \equiv \prod_{j=1}^{i}(x_{2j}-x_{j})\, (\mathrm{mod}\, N).
Причём каждая такая тройка получается из предыдущей.
2. Каждый раз, когда число i кратно числу m (скажем, m=100), вычисляется наибольший общий делитель d_{i}=\mathrm{GCD}(Q_{i},N) любым известным методом.
3. Если 1 < d_{i} < N, то частичное разложения числа N найдено, причём N = d_{i} \times (N/d_{i}).
Найденный делитель d_{i} может быть составным, поэтому его также необходимо факторизовать. Если число N/d_{i} составное, то продолжаем алгоритм с модулем N' = N/d_{i}.
4. Вычисления повторяются S раз. Если при этом число не было до конца факторизовано, выбирается, например, другое начальное число x_{0}.

Современная версия[править | править вики-текст]

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

  1. Случайным образом выбирается небольшое число x_{0}[12] и строится последовательность \{x_{n}\}, n = 0, 1, 2, ..., определяя каждое следующее как x_{n+1} = F(x_{n})\, (\mathrm{mod}\,\, N).
  2. Одновременно на каждом i-ом шаге вычисляется d = \mathrm{GCD}(N,|x_{i}-x_{j}|) для каких-либо i, j таких, что j<i, например, i = 2j.
  3. Если d>1, то вычисление заканчивается, и найденное на предыдущем шаге число d является делителем N. Если N/d не является простым числом, то процедуру поиска делителей продолжается, взяв в качестве N число N'=N/d.

На практике функция F(x) выбирается не слишком сложной для вычисления (но в то же время не линейным многочленом), при условии того, что она не должна порождать взаимно однозначное отображение. Обычно в качестве F(x) выбираются функции F(x) = x^2 \pm 1 (\mathrm{mod}\, N)[12] или F(x) = x^2 \pm a (\mathrm{mod}\, N)[13]. Однако функции x^2-2 и x^2 не подходят[10].

Если известно, что для делителя p числа N справедливо p \equiv 1\, (\mathrm{mod}\, k) при некотором k > 2, то имеет смысл использовать F(x) = x^k + b[10].

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

Улучшения алгоритма[править | править вики-текст]

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

Пусть F(x) = (x^2 - 1) \mathrm{mod}\, N. Тогда, если (x_{j} - x_{i}) \equiv 0 (\mathrm{mod}\, p), то (f(x_{j}) - f(x_{i})) \equiv 0 (\mathrm{mod}\, 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][11].

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

Ещё одна вариация ρ-алгоритма полларда была разработана Флойдом. Согласно Флойду, значение 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[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

Используя другие варианты полинома F(x), можно также получить делитель 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.

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

Обоснование ρ-алгоритма Полларда[править | править вики-текст]

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

Парадокс дней рождений, кратко:
Пусть \lambda > 0. Для случайной выборки из l+1 элементов, каждый их которых меньше q, где l = \sqrt{2 \lambda q}, вероятность того, что два элемента окажутся одинаковыми p > 1 - \exp^{-\lambda}.

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

Пусть последовательность \{u_{n}\} состоит из разностей x_{i} - x_{j}, проверяемых в ходе работы алгоритма. Определяется новая последовательность \{z_{n}\}, где z_{n} = u_{n}\, \mathrm{mod}\, q, q — меньший из делителей числа N.

Все члены последовательности \{z_{n}\} меньше \sqrt{N}. Если рассматривать её как случайную последовательность целых чисел, меньших q, то, согласно парадоксу дней рождения, вероятность того, что среди l+1 её членов попадутся два одинаковых, превысит 1/2 при \lambda \approx 0.69, тогда l должно быть не меньше \sqrt{2\lambda q} \approx \sqrt{1.4 q} \approx 1.18\sqrt{q}.

Если z_{i}=z_{j}, тогда x_{i}-x_{j} \equiv 0\, \mathrm{mod}\, q, то есть, x_{i}-x_{j}=kq для некоторого целого k. Если x_{i} \neq x_{j}, что выполняется с большой вероятностью, то искомый делитель q числа N будет найден как \mathrm{GCD}(N, |x_{i}-x_{j}|). Поскольку \sqrt{q} \leq n^{1/4}, то с вероятностью, превышающей 1/2 , делитель N будет найден за 1.18 \times N^{1/4} итераций[11].

Сложность алгоритма[править | править вики-текст]

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

Поэтому сложность алгоритма оценивается, как O(N^{1/4})[16]. Однако в этой оценке не учитываются накладные расходы по вычислению наибольшего общего делителя. Полученная сложность алгоритма, хотя и не является точной, достаточно хорошо согласуется с практикой.

Справедливо следующее утверждение: пусть N — составное число. Тогда существует такая константа C, что для любого положительного числа \lambda вероятность события, состоящего в том, что ρ-алгоритм Полларда не найдет нетривиального делителя N за время C\sqrt{\lambda \sqrt N}(\log N)^2, не превосходит величины e^{-\lambda}. Данное утверждение следует из парадокса дней рождения[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));
 }

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

Распараллеливание алгоритма[править | править вики-текст]

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

Система с распределенной памятью[править | править вики-текст]

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

Предположим что есть P одинаковых исполнителей. Если мы используем P различных последовательностей (то есть различных полиномов F(x)), то вероятность того, что первые k чисел в этих последовательностях будут различными по модулю p будет примерно равна \exp({-k^2 P}/{2 p}). Таким образом, максимальное ускорение можно оценить как P^{1/2}[9].

Ричард Крэндалл предположил, что достижимо ускорение O(P/(log{P})^2), однако данное утверждение пока не проверено[20].

Система с общей памятью[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 Pollard, 1974, с. 521–528.
  2. Christensen, 2009, 3.3.3.0.
  3. Chatterjee, 2009, 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, 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. ρ-метод Полларда.
  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.

Литература[править | править вики-текст]