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

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

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

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

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

$a^{(p-<!--\; -\; -->1)}\equiv <!--\; \equiv \; -->1\mathrm{mod}p$$a^{(p-1)}\equiv 1\mod p$ , более того $\mathrm{\forall <!--\; \forall \; -->}M=(p-<!--\; -\; -->1)l,l\in <!--\; \in \; -->N\Rightarrow <!--\; \Rightarrow \; -->a^M\equiv <!--\; \equiv \; -->1\mathrm{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$  или же, в случае простого $N$$N$ , проверке его на простоту. Нижеприведённый алгоритм явился следствием и иллюстрацией теоретических выкладок Полларда.

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

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

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

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

Вторая стадияПравить

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

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

$g_m=(F_m,N)>1$$g_{m}=(F_{m},N)>1$ 

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

ЗамечаниеПравить

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

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

Современная версияПравить

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

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

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

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

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

ПримерПравить

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

ЗамечанияПравить

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

$a_1=a^{M_1}\mathrm{mod}N;$$a_{1}=a^{M_{1}}\mod N;$ 

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

Вторая стадияПравить

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

1. Для дальнейшего нам потребуется вектор из простых чисел $q_i$$q_{i}$  от $B_1$$B_1$  до $B_2$$B_{2}$ , из которого легко получить вектор разностей между этими простыми числами $D=(D_1,D_2,...),D_i=q_{i+1}-<!--\; -\; -->q_i$$D=(D_{1},D_{2},...),D_{i}=q_{i+1}-q_{i}$ , причём $D_i$$D_{i}$  — относительно небольшие числа, и $D_i\in <!--\; \in \; -->\mathrm{\Delta <!--\; \Delta \; -->}$$D_{i}\in \Delta$ , где $\mathrm{\Delta <!--\; \Delta \; -->}$$\Delta$  — конечно множество. Для ускорения работы алгоритма полезно предварительно вычислить все $b^{{\mathrm{\delta <!--\; \delta \; -->}}_i},\mathrm{\forall <!--\; \forall \; -->}{\mathrm{\delta <!--\; \delta \; -->}}_i\in <!--\; \in \; -->\mathrm{\Delta <!--\; \Delta \; -->}$$b^{\delta _{i}},\forall \delta _{i}\in \Delta$  и при пользоваться уже готовыми значениями.
2. Теперь необходимо последовательно вычислять $c_0=b_1\mathrm{mod}N,c_i=c_{i-<!--\; -\; -->1}^{{\mathrm{\delta <!--\; \delta \; -->}}_i}\mathrm{mod}N$$c_{0}=b_{1}\mod N,c_{i}=c_{i-1}^{\delta _{i}}\mod N$ , где $b_1=a^{M(B_1)}\mathrm{mod}N$$b_{1}=a^{M(B_{1})}\mod N$ , вычисленное в первой стадии, на каждом шаге считая $G=(c_i-<!--\; -\; -->1,N)$$G=(c_{i}-1,N)$ . Как только $G\ne <!--\; \ne \; -->1$$G\neq 1$ , можно прекращать вычисления.

Условия сходимостиПравить

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

Модификации и улучшенияПравить

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

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

• Сложность первой стадии оценивается как $O(B\cdot <!--\; \cdot \; -->\ln <!--\; \; -->B\cdot <!--\; \cdot \; -->(\ln <!--\; \; -->N{)}^2+(\ln <!--\; \; -->N{)}^3)$$O(B\cdot \ln B\cdot (\ln N)^{2}+(\ln N)^{3})$ , оставляя только слагаемое высшего порядка получаем оценку первой стадии алгоритма $O(B\cdot <!--\; \cdot \; -->\ln <!--\; \; -->B\cdot <!--\; \cdot \; -->(\ln <!--\; \; -->N{)}^2)$$O(B\cdot \ln B\cdot (\ln N)^{2})$ .
• Согласно оценке Монтгомери, сложность второй стадии, с точностью до слагаемых наивысшего порядка составляет $O(\mathrm{\pi <!--\; \pi \; -->}(B_2))$$O(\pi (B_{2}))$ , где $\mathrm{\pi <!--\; \pi \; -->}(s)$$\pi (s)$  — число простых чисел, меньших $s$$s$ . Оценка Чебышева дает приближённое равенство $\mathrm{\pi <!--\; \pi \; -->}(s)\approx <!--\; \approx \; -->\frac{s}{\ln <!--\; \; -->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$$960^{119}-1$	Т. Ногара	29.06.2006	${10}^8$$10^{8}$	${10}^{10}$$10^{{10}}$
64	1939611922516629203444058938928521328695726603873690611596368359 = 2 · 3 · 11 · 1187 · 9233729 · 13761367 · 43294577 · 51593573 · 100760321 · 379192511 · 2282985164293 + 1	${10}^{243}-<!--\; -\; -->4\cdot <!--\; \cdot \; -->{10}^{121}-<!--\; -\; -->1$$10^{243}-4\cdot 10^{121}-1$	М. Тервурен	13.09.2012	${10}^9$$10^{{9}}$	${10}^{13}$$10^{13}$
59	12798830540286697738097001413455268308836003073182603569933 = 22 · 17 · 59 · 107 · 113 · 20414117 · 223034797 · 269477639 · 439758239 · 481458247 · 1015660517 + 1	${8069000260399979023963141}^{17}-<!--\; -\; -->1$$8069000260399979023963141^{17}-1$	A. Круппа	30.06.2011	${10}^9$$10^{9}$	${10}^{10}$$10^{{10}}$

ПримененияПравить

• GMP-ECM — пакет включает в себя эффективное применение $p-<!--\; -\; -->1$$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