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

Число называется ${\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}$ .

Джон Поллард впервые опубликовал описанный ниже алгоритм в своей статье «Методы факторизации и проверка простоты» («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}$ 

Эта переработанная по сравнению с оригинальной версия алгоритма использует понятия степенной гладкости^[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] во второй стадии, однако он не привел реальных способов, как сделать это^[6].
    • Ещё позже, в 1990 году это сделали математики
      • Сложность первой стадии оценивается как ${\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}$ -метода.
      • • P+1-метод Уильямса
        • 1. ↑ ^{1 2 3 4 5 6 7} Pollard, 1974.
          2. ↑ ^{1 2} Karaarslan E. Primality Testing Techniques and The Importance of Prime Numbers in Security Protocols (англ.) // ICMCA'2000: Proceedings of the Third International Symposium Mathematical & Computational Applications — Konya: 2000. — P. 280—287.
          3. ↑ Василенко, 2003, с. 60.
          4. ↑ ^{1 2 3 4 5 6 7 8 9 10 11} Ишмухаметов, 2011, с. 53—55.
          5. ↑ ^{1 2 3} Cohen, 2000, pp. 439.
          6. ↑ ^{1 2} Montgomery, Silverman, 1990.
          7. ↑ Циммерман, Поль. Record Factors Found By Pollard's p-1 Method (англ.). Les pages des personnels du LORIA et du Centre Inria NGE. Дата обращения: 10 октября 2016. Архивировано 11 октября 2016 года.
          8. ↑ InriaForge: GMP-ECM (Elliptic Curve Method): Project Home  (неопр.). Дата обращения: 15 ноября 2012. Архивировано 21 июля 2012 года.

          Литература

          • 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