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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим последовательность целых чисел {x_{n}}, такую что x_{0}=2 и x_{i+1}=(x_{i}^{2}-1\,) (\mathrm{mod}\, N), где N - число, которое нужно факторизовать. Оригинальный алгоритм выглядит следующим образом[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 раз. Например, можно прекратить алгоритм при i = S = 10^5. Если при этом число не было до конца факторизовано, можно выбрать, например, другое начальное число x_{0}.

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

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

  1. Выбираем небольшое число x_{0} и строим последовательность \{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) или F(x) = x^2 \pm a (\mathrm{mod}\, N)[8]. Однако не следует использовать функции x^2-2 и x^2[6].

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

Существенным недостатком алгоритма в такой реализации является необходимость хранить большое число предыдущих значений 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][7].

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

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

Пример факторизации числа[править | править вики-текст]

Пусть N = 8051, F(x) = (x^2 + 1)\, \mathrm{mod}\, 8051, x_0=y_0=2, y_{i+1}=F(F(y_{i})).

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

Таким образом, 97 — нетривиальный делитель числа 8051. Используя другие варианты полинома F(x), можно также получить делитель 83.

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

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

Теорема. (Парадокс дней рождения)

Пусть \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}, то с вероятностью, превышающей 0.5, делитель N будет найден за 1.18 \times N^{1/4} итераций[7].

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

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

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

Справедлива следующая теорема. Пусть 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, что выгодно отличает метод в такой реализации от других методов факторизации чисел[7].

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

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

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

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

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

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

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

  1. Флойд описывает алгоритмы поиска простых циклов в ориентированном графе в статье, опубликованной в 1976 году: Floyd, R.W. (1967), "«Non-deterministic Algorithms»", J. ACM Т. 14 (4): 636–644, doi:10.1145/321420.321422, <http://doi.acm.org/10.1145/321420.321422> . Первое описание алгоритма "черепахи и зайца" появляется в книге Knuth, Donald E. (1969), «The Art of Computer Programming, vol. II: Seminumerical Algorithms», Addison-Wesley , упражнениях 6 и 7, стр. 7. Кнут (стр.4) приписывает этот алгоритм Флойду, не ссылаясь на источники.
  2. 1 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. 1 2 Brent-1999, 1999, Some parallel algorithms for integer factorization.
  6. 1 2 3 Pollard, 1975, A Monte Carlo method for factorization
  7. 1 2 3 4 5 Ишмухаметов, 2011, Методы факторизации натуральных чисел: Учебное пособие
  8. Н.Ю. Золотых. Лекции по компьютерной алгебре. Лекция 11. ρ-метод Полларда.
  9. Reisel, 2012, Selected Areas in Cryptography. Prime Numbers and Computer Methods for Factorization. 2nd ed.
  10. Cormen, 2001, Introduction to Algorithms. Section 31.9. Integer Factorization. Pollard's rho heuristic.
  11. Crandall, 1999, Parallelization of Polldar-rho factorization

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