Просмотр кода страницы P−1-метод Полларда

{{заголовок с маленькой буквы}}
'''<math>p-1</math>-метод Полларда''' — один из методов [[Факторизация целых чисел|факторизации целых чисел]].

Впервые опубликован британским математиком {{iw|Джон Поллард|Джоном Поллардом||John Pollard (mathematician)}} в [[1974 год в науке|1974 году]]{{sfn|Pollard|1974}}. Именно появление данного алгоритма привело{{source-ref|Q27184054}} к изменению понятия [[Сильное простое число (криптография)|сильного простого числа]], используемого в [[Криптография|криптографии]], нестрого говоря, [[Простое число|простого числа]], для которого <math> p-1 </math> имеет достаточно большие делители. В современных [[криптосистема]]х стараются{{source-ref|Q27184054}} использовать именно сильные простые числа, так как это повышает [[Криптографическая стойкость|стойкость]] используемых алгоритмов и систем в целом.

== Определения и математические сведения ==
Число называется ''<math>B</math>-{{iw|гладкостепенное число|гладкостепенным|en|Powersmooth number}}''{{sfn|Василенко|2003|страницы=60}}, если все его простые делители, в степенях, в которых они входят в разложение этого числа <math> p^{\nu} </math>, удовлетворяют <math>  p^{\nu} \leq B </math>. Согласно [[Малая теорема Ферма|малой теореме Ферма]] для любого простого числа <math>p</math> и для любого целого числа <math>a</math>, такого что <math>a </math> и <math>p </math> [[Взаимно простые числа|взаимно просты]], или, что в данном случае равносильно, <math>p </math> не делит <math>a </math>, справедливо:
:: <math>a^{(p-1)} \equiv 1 \mod p </math>, более того <math>\forall M=(p-1)l, l \in N \Rightarrow a^M \equiv 1 \mod p </math>.

== Оригинальный алгоритм (1974 год) ==
Джон Поллард впервые опубликовал описанный ниже алгоритм в своей статье «Методы факторизации и проверка простоты» («Theorems of Factorization and Primality Testing») в 1974 году в «[[Mathematical Proceedings of the Cambridge Philosophical Society|Трудах Кембриджеского философского общества]]»{{sfn|Pollard|1974}}. Статья посвящена теоретической оценке [[Вычислительная сложность|сложности]] факторизации большого числа <math> N</math> или же, в случае простого <math> N</math>, проверке его на простоту. Нижеприведённый алгоритм явился следствием и иллюстрацией теоретических выкладок Полларда.

=== Первая стадия ===
# Задача состоит в том, чтобы найти собственный делитель числа <math>N</math> отличный от единицы. Прежде всего необходимо выбрать два числа <math>B, M,</math> такие, что <math> 1<B<M<\sqrt{N}, M<B^2 </math>.
# Вычислим теперь число <math>M(B) = \prod_{k=1}^{m} p_k^{c_k}</math>, где <math>p_k</math> — все простые числа меньшие <math>B </math>. Здесь допускается некоторая свобода в выборе <math>c_k</math>, однако точно известно, что для маленьких <math>p_k</math>, <math>c_k</math> должно быть больше единицы{{sfn|Pollard|1974}}.
# Выберем небольшое целое <math>a>1</math> и вычислим
::: <math>b = a^{M(B)} \mod N </math>
::: <math> q = (b-1, N) </math> если <math>q \ne 1</math> мы нашли делитель <math> N </math>, в противном случае переходим ко второй стадии.

=== Вторая стадия ===
* На этом шаге необходимо вычислить последовательность

::<math> F_m \equiv b^{m-1} - 1 \mod N, </math> где <math>m</math> — простое, <math>B < m < M </math>, надеясь, что на каком-нибудь шаге получится
:: <math> g_m = (F_m, N) > 1 </math>
* Легче всего{{sfn|Pollard|1974}} это сделать вычислением <math>b^m</math> для каждого нечётного <math>m</math> домножением на <math>b^2</math>, беря <math>G_i = (b^i,N)</math> через равные промежутки. Если <math>1 < G_i < N </math> делитель найден. Если же <math>G_i = N, G_{i-1} = 1 </math>, то необходимо точнее исследовать этот участок.

=== Замечание ===
С помощью данного метода мы сможем найти только такие простые делители <math>p </math> числа <math>N</math>, для которых выполнено{{sfn|Pollard|1974}}:

: <math>p-1 = A</math> или <math>p-1 = Aq </math>, где <math>A</math> является <math>B</math>-гладкостепенным, а <math>q</math> — простое, такое что <math>B<q<M</math>{{sfn|Pollard|1974}}.

== Современная версия ==
Эта переработанная по сравнению с оригинальной версия алгоритма использует понятия {{iw|гладкостепенное число|степенной гладкости|en|Powersmooth number}} и ориентирована на практическое применение. Значительные изменения претерпела первая стадия, в то время, как вторая сохранилась практически без изменений, опять же, с теоретической точки зрения, ничего значительного, по сравнению предыдущей версией, добавлено не было. Именно приведённый ниже алгоритм имеют в виду, когда говорят о «методе Полларда»{{sfn|Ишмухаметов|2011|страницы=53—55}}{{sfn|Cohen|2000|pp=439}}.

=== Первая стадия ===
# Пусть <math>N </math> <math>B</math>-гладкостепенное, и требуется найти делитель числа <math>N</math>. В первую очередь вычисляется число <math>M(B) = \prod_i p_i^{k_i} </math> где произведение ведётся по всем простым <math>p_i</math> в максимальных степенях <math>k_i: p_i^{k_i}<B </math>
# Тогда искомый делитель <math>q = (b - 1, N) </math>{{sfn|Ишмухаметов|2011|страницы=53—55}}, где <math>b = a^{M(B)} \mod N</math>.
* Возможно два случая, в которых приведенный выше алгоритм не даст результата{{sfn|Cohen|2000|pp=439}}.
# В случае, когда <math>(b - 1, N) = N</math> точно можно сказать, что у <math>n</math> есть делитель, являющийся <math>B</math>-гладкостепенным и проблему должен решить иной выбор <math>a</math>.
# В более частом случае, когда <math>(b - 1, N) = 1</math> стоит перейти ко второй стадии алгоритма, которая значительно повышает вероятность результата, хотя и не гарантирует его.

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

==== Замечания ====
* При больших <math>B</math> число <math>M(B)</math> может оказаться весьма большим, сравнимым по значению с <math>B!</math>, в таких случаях может оказаться целесообразно разбить <math>M(B)</math> на множители приблизительно одинаковой величины <math>M(B) = \prod_i M_i</math> и вычислять последовательность

:: <math>a_1 = a^{M_1} \mod N;</math>

:: <math>a_{k+1} = a_k^{M_{k+1}} \mod N</math>.

=== Вторая стадия ===
* Прежде всего необходимо зафиксировать границы <math>B_1 = B, B_2 \gg B</math>, обычно <math>B_2 \leq B^2</math>{{sfn|Cohen|2000|pp=439}}{{sfn|Ишмухаметов|2011|страницы=53—55}}.
* Вторая стадия алгоритма находит делители <math>N</math>, такие что <math>p-1 = q \cdot A</math>, где <math>A</math> — <math>B</math>-гладкостепенное, а <math>q</math> простое, такое что <math>B_1<q<B_2 </math>.
# Для дальнейшего нам потребуется вектор из простых чисел <math>q_i</math> от <math>B_1</math> до <math>B_2</math>, из которого легко получить вектор разностей между этими простыми числами <math>D = (D_1,D_2, ...), D_i = q_{i+1} - q_i</math>, причём <math>D_i</math> — относительно небольшие числа, и <math>D_i \in \Delta</math>, где <math>\Delta</math> — конечно множество{{sfn|Ишмухаметов|2011|страницы=53—55}}. Для ускорения работы алгоритма полезно предварительно вычислить все <math>b^{\delta_i}, \forall \delta_i \in \Delta</math>{{sfn|Ишмухаметов|2011|страницы=53—55}} и при пользоваться уже готовыми значениями.
# Теперь необходимо последовательно вычислять <math>c_0 = b_{1} \mod N, c_i = c_{i-1}^{\delta_i} \mod N</math>, где <math>b_{1} = a^{M(B_1)}\mod N</math>, вычисленное в первой стадии, на каждом шаге считая <math>G = (c_i-1, N)</math>. Как только <math>G \neq 1 </math>, можно прекращать вычисления.

== Условия сходимости ==
* Пусть <math>p</math> наименьший делитель <math>N</math>, <math>q^t = max(q_i^{t_i})</math> максимум берется по всем степеням <math>q_i^{t_i}</math>, делящим <math>p-1</math>{{sfn|Ишмухаметов|2011|страницы=53—55}}.
** Если <math>q^t < B_1</math>, то делитель будет найден на первой стадии алгоритма{{sfn|Ишмухаметов|2011|страницы=53—55}}.
** В противном случае для успеха алгоритма необходимо, чтобы <math>q^t < B_2</math>, а все остальные делители <math>p-1</math> вида <math>q^r</math> были меньше <math>B_1</math>{{sfn|Ишмухаметов|2011|страницы=53—55}}.

== Модификации и улучшения ==
* Позднее сам Поллард высказал мнение о возможности ускорения алгоритма с использованием [[Быстрое преобразование Фурье|быстрого преобразования Фурье]]{{sfn|Ишмухаметов|2011|страницы=53—55}} во второй стадии, однако он не привел реальных способов, как сделать это{{sfn|Montgomery, Silverman|1990}}.
* Ещё позже, в 1990 году это сделали математики [[Питер Монтгомери]] (Peter Montgomery) и [[Роберт Силверман]] (Robert Silverman){{sfn|Montgomery, Silverman|1990}}. Авторам удалось добиться увеличения скорости исполнения второй стадии алгоритма.

== Оценка эффективности ==
* [[Вычислительная сложность|Сложность]] первой стадии оценивается как <math>O(B \cdot \ln B \cdot (\ln N)^2 + (\ln N)^3)</math>, оставляя только слагаемое высшего порядка получаем оценку первой стадии алгоритма{{sfn|Ишмухаметов|2011|страницы=53—55}} <math>O(B \cdot \ln B \cdot (\ln N)^2)</math>.
* Согласно оценке Монтгомери, сложность второй стадии, с точностью до слагаемых наивысшего порядка составляет <math>O(\pi (B_2))</math>{{sfn|Pollard|1974}}{{sfn|Ишмухаметов|2011|страницы=53—55}}, где <math>\pi (s)</math> — число простых чисел, меньших <math>s</math>. [[Теорема о распределении простых чисел|Оценка Чебышева]] дает приближённое равенство <math>\pi (s) \approx \frac{s}{\ln s}</math>.

== Рекорды ==
На данный момент (10.10.2016) три самых больших [[Простой множитель|простых делителя]], найденных методом P-1, состоят из 66, 64 и 59 десятичных цифр<ref name="records">{{cite web
|author=[[Циммерман, Поль]]
|url=https://members.loria.fr/PZimmermann/records/Pminus1.html
|title=Record Factors Found By Pollard's p-1 Method
|lang=en
|publisher=Les pages des personnels du LORIA et du Centre Inria NGE
|access-date=2016-10-10
|archive-date=2016-10-11
|archive-url=https://web.archive.org/web/20161011060653/https://members.loria.fr/PZimmermann/records/Pminus1.html
|deadlink=no
}}</ref>.
{| class="wikitable"
|-
! Кол-во цифр
! p
! Делитель числа
! Кем найден
! Когда найден
! B
! B2
|-
| 66
| 672038771836751227845696565342450315062141551559473564642434674541
: = 2<sup>2</sup> · 3 · 5 · 7 · 17 · 23 · 31 · 163 · 401 · 617 · 4271 · 13681 · 22877 · 43397 · 203459 · 1396027 · 6995393 · 13456591 · 2110402817 + 1
| <math>960^{119}-1</math>
| Т. Ногара
| 29.06.2006
| <math>10^8</math>
| <math>10^{10}</math>
|-
| 64
| 1939611922516629203444058938928521328695726603873690611596368359
: = 2 · 3 · 11 · 1187 · 9233729 · 13761367 · 43294577 · 51593573 · 100760321 · 379192511 · 2282985164293 + 1
| <math>10^{243}-4\cdot10^{121}-1</math>
| М. Тервурен
| 13.09.2012
| <math>10^{9}</math>
| <math>10^{13}</math>
|-
| 59
| 12798830540286697738097001413455268308836003073182603569933
: = 2<sup>2</sup> · 17 · 59 · 107 · 113 · 20414117 · 223034797 · 269477639 · 439758239 · 481458247 · 1015660517 + 1
| <math>8069000260399979023963141^{17}-1</math>
| A. Круппа
| 30.06.2011
| <math>10^9</math>
| <math>10^{10}</math>
|}

== Применения ==
* GMP-ECM<ref>{{Cite web |url=http://gforge.inria.fr/projects/ecm/ |title=InriaForge: GMP-ECM (Elliptic Curve Method): Project Home<!-- Заголовок добавлен ботом --> |access-date=2012-11-15 |archive-date=2012-07-21 |archive-url=https://web.archive.org/web/20120721232351/https://gforge.inria.fr/projects/ecm/ |deadlink=no }}</ref> — пакет включает в себя эффективное применение <math>p-1</math>-метода.
* [[Prime95]] и MPrime — официальные клиенты [[GIMPS]] — используют метод, чтобы отсеять кандидатов.

== См. также ==
{{Навигация}}
* [[P+1-метод Уильямса]]
* [[Ро-алгоритм Полларда]]

== Примечания ==
{{примечания|2}}

== Литература ==
* {{source|Q27095084|ref=Pollard|ref-year=1974}} <!-- Theorems on factorization and primality testing // Mathematical Proceedings of the Cambridge Philosophical Society -->
* {{source|Q27095334|ref=Cohen|ref-year=2000}} <!-- A Course in Computational Algebraic Number Theory -->
* {{source|Q22304550|ref=Василенко|ref-year=2003}} <!-- Теоретико-числовые алгоритмы в криптографии -->
* {{source|Q27048273|ref=Ишмухаметов|ref-year=2011|pages = 53—55}} <!-- Методы факторизации натуральных чисел: учебное пособие -->
* {{source|Q27095017|ref=Montgomery, Silverman|ref-year=1990}} <!-- An FFT extension to the P-1 factoring algorithm // Math. Comp. -->

[[Категория:Алгоритмы факторизации]]