(p-1)-алгоритм Полларда

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

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

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

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

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

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

Джон Поллард впервые опубликовал описанный ниже алгоритм в своей статье «Методы факторизации и проверка простоты» («Theorems of Factorization and Primality Testing») в 1974 году в «Трудах Кембриджеского философского общества»^[1]. Статья посвящена теоретической оценке сложности факторизации большого числа ${\displaystyle N}$ или же, в случае простого ${\displaystyle N}$, проверке его на простоту. Нижеприведённый алгоритм явился следствием и иллюстрацией теоретических выкладок Полларда.

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

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

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

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

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

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

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

${\displaystyle g_{m}=(F_{m},N)>1}$

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

Замечание

С помощью данного метода мы сможем найти только такие простые делители ${\displaystyle p}$ числа ${\displaystyle N}$, для которых выполнено^[1]:

${\displaystyle p-1=A}$ или ${\displaystyle p-1=Aq}$, где ${\displaystyle A}$ является ${\displaystyle B}$-гладкостепенным, а ${\displaystyle q}$ — простое, такое что ${\displaystyle B<q<M}$^[1].

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

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

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

1. Пусть ${\displaystyle N}$ ${\displaystyle B}$-гладкостепенное, и требуется найти делитель числа ${\displaystyle N}$. В первую очередь вычисляется число ${\displaystyle M(B)=\prod _{i}p_{i}^{k_{i}}}$ где произведение ведётся по всем простым ${\displaystyle p_{i}}$ в максимальных степенях ${\displaystyle k_{i}:p_{i}^{k_{i}}<B}$
2. Тогда искомый делитель ${\displaystyle q=(b-1,N)}$^[4], где ${\displaystyle b=a^{M(B)}\mod N}$.

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

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

Пример

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

Замечания

• При больших ${\displaystyle B}$ число ${\displaystyle M(B)}$ может оказаться весьма большим, сравнимым по значению с ${\displaystyle B!}$, в таких случаях может оказаться целесообразно разбить ${\displaystyle M(B)}$ на множители приблизительно одинаковой величины ${\displaystyle M(B)=\prod _{i}M_{i}}$ и вычислять последовательность

${\displaystyle a_{1}=a^{M_{1}}\mod N;}$

${\displaystyle a_{k+1}=a_{k}^{M_{k+1}}\mod N}$.

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

• Прежде всего необходимо зафиксировать границы ${\displaystyle B_{1}=B,B_{2}\gg B}$, обычно ${\displaystyle B_{2}\leq B^{2}}$^[5][4].
• Вторая стадия алгоритма находит делители ${\displaystyle N}$, такие что ${\displaystyle p-1=q\cdot A}$, где ${\displaystyle A}$ — ${\displaystyle B}$-гладкостепенное, а ${\displaystyle q}$ простое, такое что ${\displaystyle B_{1}<q<B_{2}}$.

1. Для дальнейшего нам потребуется вектор из простых чисел ${\displaystyle q_{i}}$ от ${\displaystyle B_{1}}$ до ${\displaystyle B_{2}}$, из которого легко получить вектор разностей между этими простыми числами ${\displaystyle D=(D_{1},D_{2},...),D_{i}=q_{i+1}-q_{i}}$, причём ${\displaystyle D_{i}}$ — относительно небольшие числа, и ${\displaystyle D_{i}\in \Delta }$, где ${\displaystyle \Delta }$ — конечно множество^[4]. Для ускорения работы алгоритма полезно предварительно вычислить все ${\displaystyle b^{\delta _{i}},\forall \delta _{i}\in \Delta }$^[4] и при пользоваться уже готовыми значениями.
2. Теперь необходимо последовательно вычислять ${\displaystyle c_{0}=b_{1}\mod N,c_{i}=c_{i-1}^{\delta _{i}}\mod N}$, где ${\displaystyle b_{1}=a^{M(B_{1})}\mod N}$, вычисленное в первой стадии, на каждом шаге считая ${\displaystyle G=(c_{i}-1,N)}$. Как только ${\displaystyle G\neq 1}$, можно прекращать вычисления.

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

• Пусть ${\displaystyle p}$ наименьший делитель ${\displaystyle N}$, ${\displaystyle q^{t}=max(q_{i}^{t_{i}})}$ максимум берется по всем степеням ${\displaystyle q_{i}^{t_{i}}}$, делящим ${\displaystyle p-1}$^[4].
  • Если ${\displaystyle q^{t}<B_{1}}$, то делитель будет найден на первой стадии алгоритма^[4].
  • В противном случае для успеха алгоритма необходимо, чтобы ${\displaystyle q^{t}<B_{2}}$, а все остальные делители ${\displaystyle p-1}$ вида ${\displaystyle q^{r}}$ были меньше ${\displaystyle B_{1}}$^[4].

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

• Позднее сам Поллард высказал мнение о возможности ускорения алгоритма с использованием быстрого преобразования Фурье^[4] во второй стадии, однако он не привел реальных способов, как сделать это^[6].
• Ещё позже, в 1990 году это сделали математики Питер Монтгомери (Peter Montgomery) и Роберт Силверман (Robert Silverman)^[6]. Авторам удалось добиться увеличения скорости исполнения второй стадии алгоритма.

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

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

Рекорды

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

Кол-во цифр	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	${\displaystyle 960^{119}-1}$	Т. Ногара	29.06.2006	${\displaystyle 10^{8}}$	${\displaystyle 10^{10}}$
64	1939611922516629203444058938928521328695726603873690611596368359 = 2 · 3 · 11 · 1187 · 9233729 · 13761367 · 43294577 · 51593573 · 100760321 · 379192511 · 2282985164293 + 1	${\displaystyle 10^{243}-4\cdot 10^{121}-1}$	М. Тервурен	13.09.2012	${\displaystyle 10^{9}}$	${\displaystyle 10^{13}}$
59	12798830540286697738097001413455268308836003073182603569933 = 22 · 17 · 59 · 107 · 113 · 20414117 · 223034797 · 269477639 · 439758239 · 481458247 · 1015660517 + 1	${\displaystyle 8069000260399979023963141^{17}-1}$	A. Круппа	30.06.2011	${\displaystyle 10^{9}}$	${\displaystyle 10^{10}}$

Применения

• GMP-ECM^[8] — пакет включает в себя эффективное применение ${\displaystyle 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 (англ.) // Math. Comp. — AMS, 1990. — Vol. 54, Iss. 190. — P. 839—854. — ISSN 0025-5718; 1088-6842 — doi:10.1090/S0025-5718-1990-1011444-3