p−1-метод Полларда

$p-1$-метод Полларда — один из методов факторизации целых чисел.

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

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

Число называется $B$-гладкостепенным, если все его простые делители, в степенях, в которых они входят в разложение этого числа $p^{\nu }$, удовлетворяют $p^{\nu }\leq B$. Согласно малой теореме Ферма для любого простого числа $p$ и для любого целого числа $a$, такого что $a$ и $p$ взаимно просты, или, что в данном случае равносильно, $p$ не делит $a$, справедливо:

$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$ отличный от единицы. Прежде всего необходимо выбрать два числа $B,M,$ такие, что $1<B<M<{\sqrt {N}},M<B^{2}$.
2. Вычислим теперь число $M(B)=\prod _{k=1}^{m}p_{k}^{c_{k}}$, где $p_{k}$ — все простые числа меньшие $B$. Здесь допускается некоторая свобода в выборе $c_{k}$, однако точно известно, что для маленьких $p_{k}$, $c_{k}$ должно быть больше единицы.
3. Выберем небольшое целое $a>1$ и вычислим

$b=a^{M(B)}\mod N$

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

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

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

$F_{m}\equiv b^{m-1}-1\mod N,$ где $m$ — простое, $B<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$ является $B$-гладкостепенным, а $q$ — простое, такое что $B<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=(b-1,N)$, где $b=a^{M(B)}\mod N$.

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

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

Пример

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

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

• Прежде всего необходимо зафиксировать границы $B_{1}=B,B_{2}\gg B$, обычно $B_{2}\leq B^{2}$.
• Вторая стадия алгоритма находит делители $N$, такие что $p-1=q\cdot A$, где $A$ — $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_{1}\mod N,c_{i}=c_{i-1}^{\delta _{i}}\mod N$, где $b_{1}=a^{M(B_{1})}\mod N$, вычисленное в первой стадии, на каждом шаге считая $G=(c_{i}-1,N)$. Как только $G\neq 1$, можно прекращать вычисления.

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

• Пусть $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(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$. Оценка Чебышева дает приближённое равенство $\pi (s)\approx {\frac {s}{\ln s}}$.

Рекорды

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

Кол-во цифр	p	Делитель числа	Кем найден	Когда найден	B	B2
66	672038771836751227845696565342450315062141551559473564642434674541 = 22 · 3 · 5 · 7 · 17 · 23 · 31 · 163 · 401 · 617 · 4271 · 13681 · 22877 · 43397 · 203459 · 1396027 · 6995393 · 13456591 · 2110402817 + 1	$960^{119}-1$	Т. Ногара	29.06.2006	$10^{8}$	$10^{10}$
64	1939611922516629203444058938928521328695726603873690611596368359 = 2 · 3 · 11 · 1187 · 9233729 · 13761367 · 43294577 · 51593573 · 100760321 · 379192511 · 2282985164293 + 1	$10^{243}-4\cdot 10^{121}-1$	М. Тервурен	13.09.2012	$10^{9}$	$10^{13}$
59	12798830540286697738097001413455268308836003073182603569933 = 22 · 17 · 59 · 107 · 113 · 20414117 · 223034797 · 269477639 · 439758239 · 481458247 · 1015660517 + 1	$8069000260399979023963141^{17}-1$	A. Круппа	30.06.2011	$10^{9}$	$10^{10}$

Применения

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

См. также

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

Литература

• Pollard J. M. Theorems on factorization and primality testing (англ.) // Mathematical Proceedings of the Cambridge Philosophical Society / B. J. Green — Cambridge University Press, 1974. — Vol. 76, Iss. 3. — P. 521—528. — 8 p. — ISSN 0305-0041; 1469-8064 — doi:10.1017/S0305004100049252
• Коэн А. A Course in Computational Algebraic Number Theory — 4th Print Edition — Берлин, Гейдельберг, Нью-Йорк: Springer, 2000. — 550 с. — (Graduate Texts in Mathematics) — ISBN 978-3-540-55640-4 — ISSN 0072-5285; 2197-5612
• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии — М.: МЦНМО, 2003. — 328 с. — ISBN 978-5-94057-103-2
• Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие — Казань: Казанский университет, 2011. — С. 53—55. — 190 с.
• Montgomery P., Silverman R. D. An FFT extension to the P-1 factoring algorithm (англ.) // Mathematics of Computation — AMS, 1990. — Vol. 54, Iss. 190. — P. 839—854. — ISSN 0025-5718; 1088-6842 — doi:10.1090/S0025-5718-1990-1011444-3