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

Эта статья — о факторизации чисел. О методе дискретного логарифмирования см. Ρ-метод Полларда дискретного логарифмирования.

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

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

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

Содержание

1 История алгоритма
2 Описание алгоритма
3 Обоснование P-метода Полларда
4 Сложность алгоритма
5 Особенности реализации
- 5.1 Распараллеливание алгоритма
6 См. также
7 Примечания
8 Литература

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

В конце 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]

Выбираем небольшое число $x_{0}$ и строим последовательность $\{x_{n}\}, n = 0, 1, 2, ...$ , определяя каждое следующее как $x_{n+1} = F(x_{n})\, (\mathrm{mod}\,\, n)$ .
Одновременно на каждом i-ом шаге вычисляем $d = \mathrm{GCD}(n,|x_{i}-x_{j}|)$ для каких-либо $i$ , $j$ таких, что $j<i$ , например, $i = 2j$ .
Если обнаружили, что $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	x_i	y_i	НОД(\|x_i − y_i\|, 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)^3$ , не превосходит величины $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].

См. также

Примечания

↑ Флойд описывает алгоритмы поиска простых циклов в ориентированном графе в статье, опубликованной в 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) приписывает этот алгоритм Флойду, не ссылаясь на источники.
↑ ¹ ² Brent, 1980, An Improved Monte Carlo Factorization Algorithm
↑ Koshy, 2007, Elementary Number Theory with Applications
↑ Childs, 2009, A Concrete Introduction to Higher Algebra
↑ ¹ ² Brent-1999, 1999, Some parallel algorithms for integer factorization.
↑ ¹ ² ³ Pollard, 1975, A Monte Carlo method for factorization
↑ ¹ ² ³ ⁴ ⁵ Ишмухаметов, 2011, Методы факторизации натуральных чисел: Учебное пособие
↑ Н.Ю. Золотых. Лекции по компьютерной алгебре. Лекция 11. ρ-метод Полларда.
↑ Reisel, 2012, Selected Areas in Cryptography. Prime Numbers and Computer Methods for Factorization. 2nd ed.
↑ Cormen, 2001, Introduction to Algorithms. Section 31.9. Integer Factorization. Pollard's rho heuristic.
↑ Crandall, 1999, Parallelization of Polldar-rho factorization

Литература

Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: Учебное пособие. — Казань: Казанский Университет, 2011. — С. 61-64. — 190 с.
Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4
Ю.П. Соловьев, В.А. Садовничий, Е.Т. Шавгулидзе, В.В. Белокуров. Эллиптические кривые и современные алгоритмы теории чисел. Москва – Ижевск: Институт компьютерных исследований, 2003.
Brent, Richard P. (1980), "«An Improved Monte Carlo Factorization Algorithm»", BIT Т. 20: 176–184, doi:10.1007/BF01933190, <http://wwwmaths.anu.edu.au/~brent/pd/rpb051i.pdf>
Brent R.P. Некоторые параллельные алгоритмы факторизации чисел (англ.) = Some parallel algorithms for integer factorization. — 1999. — С. 7. — DOI:10.1017/S0305004100049252
Childs, Lindsay N. Congruences // Введение в высшую алгебру = Concrete Introduction to Higher Algebra. — 3-е изд. — USA: Springer, 2009. — С. 471-473. — 603 с. — ISBN 978-0-387-74725-5
Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Алгоритмы: построение и анализ = Introduction to algorithms. — 2-е изд. — USA: MIT Press, 2001. — С. 897-907. — 1180 с. — ISBN 9780262032933
Crandall R.E. Распараллеливание P-алгоритма факторизации Полларда (англ.) = Parallelization of Polldar-rho factorization. — 1999.
Koshy T. Congruences // Элементарная теория чисел и ее приложения = Elementary Number Theory with Applications. — 2-е изд. — USA: Academic Press, 2007. — С. 238. — 771 с. — ISBN 9780123724878
Pollard, J. M. (1975), "«A Monte Carlo method for factorization»", BIT Numerical Mathematics Т. 15 (3): 331–334, <http://www.cs.cmu.edu/~avrim/451f11/lectures/lect1122_Pollard.pdf>
Pollard J. M. Методы факторизации и проверка простоты. (англ.) = Theorems on factorization and primality testing. // Математические Труды Кэмбриджского Философского Общества (Mathematical Proceedings of the Cambridge Philosophical Society). — 1974. — Т. 76. — № 3. — С. 521. — DOI:10.1017/S0305004100049252
Reisel, H. Простые числа и компьютерные методы факторизации = Prime Numbers and Computer Methods for Factorization. — 2-е изд. — USA: Springer, 2012. — С. 183. — 464 с. — ISBN 978-0-8176-8297-2

Эта статья выставлена на рецензию.
Пожалуйста, выскажите своё мнение о ней на подстранице рецензии.

Категория:

Алгоритмы факторизации

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Полезное

Смотреть что такое "Ρ-алгоритм Полларда" в других словарях:

Алгоритм Шенкса — (англ. Baby step giant step; также называемый алгоритм больших и малых шагов) в теории групп, детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный… … Википедия
Алгоритм Фюрера — (англ. Fürer’s algorithm) быстрый метод умножения больших целых чисел. Алгоритм был построен в 2007 году швейцарским математиком Мартином Фюрером[1] из университета штата Пенсильвания как асимптотически более быстрый алгоритм, чем его… … Википедия
Алгоритм Диксона — Алгоритм Диксона алгоритм факторизации, использующий в своей основе идею Лежандра, заключающуюся в поиске пары целых чисел и таких, что и Метод Диксона является обобщением метода Ферма. Содержание 1 … Википедия
Rho-алгоритм Полларда — … Википедия
P-1 метод Полларда — (читается как п 1 метод Полларда) один из методов факторизации целых чисел. Метод был впервые опубликован британским математиком Джоном М. Поллардом в 1974 году в статье журнала Математические Труды Кэмбриджеского Философского… … Википедия
Ρ-метод Полларда дискретного логарифмирования — ρ метод Полларда для дискретного логарифмирования алгоритм дискретного логарифмирования в кольце вычетов по простому модулю, имеющий экспоненциальную сложность. Он был предложен Поллардом в 1978 году. Основные идеи алгоритма очень… … Википедия
Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия
Программируемые алгоритмы — Служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавл … Википедия
Метод квадратичных форм Шенкса — метод факторизации целых чисел, основанный на применении квадратичных форм, разработанный Даниелем Шенксом (англ. Daniel Shanks).[1] в 1975 году, как развитие метода факторизации Ферма. Для 32 разрядных компьютерах алгоритмы, основанные на… … Википедия
Тест простоты Люка — В теории чисел тест простоты Люка это тест простоты натурального числа n; для его работы необходимо знать разложение на множители. Для простого числа n простые множители числа вместе с некоторым основанием a составляют сертификат Пратта, который… … Википедия

Словари и энциклопедии на Академике

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

Содержание

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