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

Шаблон:Заголовок с маленькой буквы $p-1$-метод Полларда — один из методов факторизации целых чисел.

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

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

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

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

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

Джон Поллард впервые опубликовал описанный ниже алгоритм в своей статье «Методы факторизации и проверка простоты» («Theorems of Factorization and Primality Testing») в 1974 году в «Трудах Кембриджеского философского общества»Шаблон:Sfn. Статья посвящена теоретической оценке сложности факторизации большого числа $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$ должно быть больше единицыШаблон:Sfn.
3. Выберем небольшое целое $a>1$ и вычислим

$b=a^{M(B)}modN$

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

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

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

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

$g_m=(F_m,N)>1$

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

Замечание

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

$p-1=A$ или $p-1=Aq$, где $A$ является $B$-гладкостепенным, а $q$ — простое, такое что $B<q<M$Шаблон:Sfn.

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

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

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

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)$Шаблон:Sfn, где $b=a^{M(B)}modN$.

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

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)}modN=2^{2520}mod10001=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}modN;$

$a_{k+1}=a_k^{M_{k+1}}modN$.

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

• Прежде всего необходимо зафиксировать границы $B_1=B,B_2\gg B$, обычно $B_2\le B^2$Шаблон:SfnШаблон:Sfn.
• Вторая стадия алгоритма находит делители $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 \mathrm{\Delta }$, где $\mathrm{\Delta }$ — конечно множествоШаблон:Sfn. Для ускорения работы алгоритма полезно предварительно вычислить все $b^{{\delta }_i},\mathrm{\forall }{\delta }_i\in \mathrm{\Delta }$Шаблон:Sfn и при пользоваться уже готовыми значениями.
2. Теперь необходимо последовательно вычислять $c_0=b_{1}modN,c_i=c_{i-1}^{{\delta }_i}modN$, где $b_1=a^{M(B_1)}modN$, вычисленное в первой стадии, на каждом шаге считая $G=(c_i-1,N)$. Как только $G\ne 1$, можно прекращать вычисления.

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

• Пусть $p$ наименьший делитель $N$, $q^t=max(q_i^{t_i})$ максимум берется по всем степеням $q_i^{t_i}$, делящим $p-1$Шаблон:Sfn.
  • Если $q^t<B_1$, то делитель будет найден на первой стадии алгоритмаШаблон:Sfn.
  • В противном случае для успеха алгоритма необходимо, чтобы $q^t<B_2$, а все остальные делители $p-1$ вида $q^r$ были меньше $B_1$Шаблон:Sfn.

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

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

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

• Сложность первой стадии оценивается как $O(B\cdot \ln B\cdot (\ln N{)}^2+(\ln N{)}^3)$, оставляя только слагаемое высшего порядка получаем оценку первой стадии алгоритмаШаблон:Sfn $O(B\cdot \ln B\cdot (\ln N{)}^2)$.
• Согласно оценке Монтгомери, сложность второй стадии, с точностью до слагаемых наивысшего порядка составляет $O(\pi (B_2))$Шаблон:SfnШаблон:Sfn, где $\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-метод Уильямса
• Ро-алгоритм Полларда

Литература

• Шаблон:Source
• Шаблон:Source
• Шаблон:Source
• Шаблон:Source
• Шаблон:Source