P-1 метод Полларда

P-1 метод Полларда (читается как п-1 метод Полларда) — один из методов факторизации целых чисел.

Метод был впервые опубликован британским математиком Джоном М. Поллардом в 1974 году в статье журнала Математические Труды Кэмбриджеского Философского Общества. Алгоритм имеет ограниченную применимость, то есть не всегда дает результат, в частности, он не приведет к успеху, если наименьший из делителей числа $n$, искомое $p$ — сильное простое число.

Исторически, именно появление данного алгоритма привело к изменению понятия сильного простого числа, используемого в криптографии, нестрого говоря, простого числа, для которого $p-1$ имеет достаточно большие делители. В современных криптосистемах стараются использовать именно сильные простые числа, так как это повышает стойкость используемых алгоритмов и систем в целом.

Определения и математические сведения

• Определение: Число называется гладким степени $B$, если все его простые делители, в степенях, в которых они входят в разложение этого числа, меньше $B$.
• Согласно малой теореме Ферма для любого простого числа $~ p$ и для любого целого числа $~ a$, такого что $~a$ и $~ p$ взаимно просты, или, что в данном случае равносильно, $~ a$ не делит $~ p$, справедливо:

$~a^{(p-1)} \equiv 1 \mod p$, более того $~ \forall M=(p-1)l, l \in N \Rightarrow a^M \equiv 1 \mod p$.

Оригинальный алгоритм (1974 год)

Джон Поллард впервые опубликовал описанный ниже алгоритм в своей статье «Методы факторизации и проверка простоты»(«Theorems of Factorization and Primality Testing») в третьем выпуске журнала Труды Кэмбриджеского Философского Общества за 1974 год. Статья посвящена теоретической оценке сложности факторизации большого числа $n$ или же, в случае простого $n$, проверке его на простоту. Нижеприведённый алгоритм явился следствием и иллюстрацией теоретических выкладок Полларда. В связи с чем данная версия имеет скорее теоретическое значение, на практике пользуются современной версией алгоритма, более удобной для реализации.

Первая стадия

1. Задача состоит в том, чтобы найти делитель числа $~N$ отличный от единицы. Прежде всего необходимо выбрать 2 числа $~L, M,$, такие, что $1<L<M<\sqrt{N}, M<L^2$.
2. Вычислим теперь число $~P = \prod_{k=1}^{m} p_k^{c_k}$, где $~p_k$ — все простые числа меньшие $~L$. Здесь допускается некоторая свобода в выборе $~c_k$, однако точно известно, что для маленьких $~p_k$, $~c_k$ должно быть больше единицы.
3. Выберем небольшое целое $a>1$ и вычислим

$~b = a^P \mod N$

$C = (b-1, N)$ если $C \ne 1$ мы нашли делитель $N$, в противном случае переходим ко второй стадии.

Вторая стадия

• На этом шаге необходимо вычислить последовательность

$F_m \equiv b^{m-1} - 1 \mod N$ где $~m$ — простое, $~L < m < M$, надеясь, что на каком-нибудь шаге получится

$g_m = (F_m, N) > 1$

• Легче всего это сделать вычислением $~b^m$ для каждого нечётного $~m$ домножением на $~b^2$, беря $~G_i = (b^i,N)$ через равные промежутки. Если $~ 1 < G_i < N$ делитель найден. Если же $~G_i = N, G_{i-1} = 1$, то необходимо точнее исследовать этот участок.

Замечание

С помощью данного метода мы сможем найти только такие простые делители $~ p$ числа $~N$, для которых выполнено:

$~ p-1 = A$ или $~ p-1 = Aq$, где $~A$ является $L$-гладким, а $q$ — простое, такое что $L<q<M$.

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

Эта переработанная по сравнению с оригинальной версия алгоритма использует понятия гладкости и ориентирована на практическое применение. Значительные изменения претерпела первая стадия, в то время, как вторая сохранилась практически без изменений, опять же, с теоретической точки зрения, ничего значительного, по сравнению предыдущей версией, добавлено не было. Именно приведённый ниже алгоритм имеют в виду, когда говорят о «методе Полларда».

Первая стадия

1. Пусть $~n$ гладкое степени $~B$, и требуется найти делитель числа $~n$. В первую очередь вычисляется число $~ M(B) = \prod_i p_i^{k_i}$ где произведение ведётся по всем простым $~p_i$ в максимальных степенях $~ k_i: p_i^{k_i}<B$
2. Тогда искомый делитель $~q = (a^{M(B)} - 1, n)$.

Пример

Пусть $~ n = 10 001$ выберем $~ B = 10$, тогда $~M(B) = 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520$, возьмём $~a = 2$ и вычислим теперь $~a^{M(B)} = 2^{2520} \mod 10001 = 3578$, и наконец $~(a^{M(B)} - 1, n) = (2^{2520} - 1, 10 001) = 73$.

Замечания

• При больших $~B$ число $~M(B)$ может оказаться весьма большим, сравнимым по значению с $~B!$, в таких случаях может оказаться целесообразно разбить $~M(B)$ на множители приблизительно одинаковой величины $~M(B) = \prod_i M_i$ и вычислять последовательность

$~ a_1 = a^{M_1} \mod n;$

$~ a_{k+1} = a_k^{M_{k+1}} \mod n$.

• Возможно два случая, в которых приведенный выше алгоритм не даст результата.

1. В случае, когда $~(a^{M(B)} - 1, n) = n$ точно можно сказать, что у $~n$ есть делитель, являющийся гладким степени $~B$ и проблему должен решить иной выбор $~a$.
2. В более частом случае, когда $~(a^{M(B)} - 1, n) = 1$ стоит перейти ко второй стадии алгоритма, которая значительно повышает вероятность результата, хотя и не гарантирует его.

Вторая стадия

• Прежде всего необходимо зафиксировать границы $~B_1 = B, B_2 \gg B$, обычно $~B_2 \leq B^2$.
• Вторая стадия алгоритма находит делители $~ n$, такие что $~ p-1 = q \cdot f$, где $~ f$ — гладкое степени $~B$, а $~q$ простое, такое что $~B_1<q<B_2$.

1. Для дальнейшего нам потребуется вектор из простых чисел $~q_i$ от $~B_1$ до $~B_2$, из которого легко получить вектор разностей между этими простыми числами $~ D = (D_1,D_2, ... ), D_i = q_{i+1} - q_i$, причем $~D_i$ — относительно небольшие числа, и $~D_i \in \Delta$, где $~\Delta$ — конечно множество . Для ускорения работы алгоритма полезно предварительно вычислить все $~b^{\delta_i}, \forall \delta_i \in \Delta$ и при пользоваться уже готовыми значениями.
2. Теперь необходимо последовательно вычислять $~ c_0 = b \mod n, c_i = c_{i-1}^{\delta_i} \mod n$, где $~ b = a^M(B_1) \mod n$, вычисленное в первой стадии, на каждом шаге считая $~Q = (c_i-1, n)$. Как только $~Q \neq 1$, можно прекращать вычисления.

Условия сходимости

• Если $~n$ является произведением двух сильных простых чисел $~p,q$, причем $~q<p, q>2B+1$, то $~(\rho-1)$-алгоритм Полларда не факторизует $~n$.
• Пусть $~p$ наименьший делитель $~n$, $~q^t = max(q_i^{t_i})$ максимум берется по всем степеням $~q_i^{t_i}$, делящим $~p-1$.
  • Если $~q^t < B_1$, то делитель будет найден на первой стадии алгоритма.
  • В противном случае для успеха алгоритма необходимо, чтобы $~q^t < B_2$, а все остальные делители $~p-1$ вида $~q^r$ были меньше $~B_1$.

Модификации и улучшения

• Позднее сам Поллард высказал мнение о возможности ускорения алгоритма с использованием быстрого преобразования Фурье во второй стадии, однако он не привел реальных способов, как сделать это.
• Ещё позже, в [1990] году это сделали математики Питер Монтгомери (Peter Montgomery) и Роберт Силверман (Robert Silverman). Авторам удалось добиться скорости исполнения алгоритма второй стадии алгоритма $~ O(k \ln(n)( \lg (k)+ \lg (n))$.

Оценка эффективности

• Сложность первой стадии оценивается как $~O(B \cdot \ln B \cdot (\ln n)^2 + (\ln n)^3)$, оставляя только слагаемое высшего порядка получаем оценку первой стадии алгоритма $~O(B \cdot \ln B \cdot (\ln n)^2)$.
• Согласно оценке Монтгомери, сложность второй стадии, с точностью до слагаемых наивысшего порядка составляет $~O(\pi (B_2))$ , где $~\pi (s), s\in \Z$ — число простых чисел, меньших $~s$. оценка Чебышева дает приближённое равенство $~\pi (s) \approx \frac{s}{\ln s}$.

Рекорды

На данный момент (09.12.2008) три самых больших простых делителя, найденных методом P-1, состоят из 66, 58 и 57 десятичных цифр.

Кол-во цифр	p, p-1	Делитель числа	Найден (кем)	Найден (когда)	B	B2
66	672038771836751227845696565342450315062141551559473564642434674541 2².3.5.7.17.23.31.163.401.617.4271.13681.22877.43397.203459.1396027.6995393.13456591.2110402817	960^119-1	T. Nohara	29.06.2006	10^8	10^10
58	1372098406910139347411473978297737029649599583843164650153 2³.3².1049.1627.139999.1284223.7475317.341342347.2456044907.9909876848747	2^2098+1	P. Zimmermann	28.09.2005	10^10	10^13
57	357561419933316305231935975632510092006707198190314688497 2^4.3².11.31.612.2131.7703.102199.12170281.294393133.346193663.940452192083	6^396+1	P. Zimmermann	31.10.2003	10^9	10^12

Применения

• GMP-ECM (англ.) — Пакет включает в себя эффективное применение P-1 метода.
• Prime95 (англ.) и MPrime (англ.) — официальные клиенты GIMPS используют метод, чтобы отсеять кандидатов.

См. также

• P+1 метод Уильямса
• Ρ-алгоритм Полларда

Литература

• Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: Учебное пособие. — Казань: Казанский Университет, 2011. — С. 53-55. — 190 с.
• Pollard J. M. Методы факторизации и проверка простоты. (англ.) = Theorems on factorization and primality testing. // Математические Труды Кэмбриджского Философского Общества (Mathematical Proceedings of the Cambridge Philosophical Society). — 1974. — Т. 76. — № 3. — С. 521. — DOI:10.1017/S0305004100049252
• Cohen H. A. Курс по Вычислительной Алгебраической Теории Чисел = A Course in Computational Algebraic Number Theory.. — Berlin ; Heildelberg ; New York: Springer, 2000. — С. С. 439. — 550 с. — ISBN 3-54055-640-0
• Montgomery P. L.; Silverman R. D. Продолжение Р-1 алгоритма факторизации с применением БПФ (An FFT extension to the P-1 factoring algorithm) (англ.) // Математика Вычислений (Mathematics of Computation) : журнал. — 1990. — Т. 54. — № 190. — С. 839-854. — DOI:10.1090/S0025-5718-1990-1011444-3
• Karaarslan E. Способы Проверки на Простоту и Важность Простых Чисел в Защищенных Протоколах (англ.) = Primality Testing Techniques and The Importance of Prime Numbers in Security Protocols // Материалы 3й Международной Конференции Математических и Вычислительных Приложений (ICMCA 2002). — Турция, 2002. — С. 1-2.