Русская Википедия:P−1-метод Полларда
Шаблон:Заголовок с маленькой буквы <math>p-1</math>-метод Полларда — один из методов факторизации целых чисел.
Впервые опубликован британским математиком Шаблон:Iw в 1974 годуШаблон:Sfn. Именно появление данного алгоритма привелоШаблон:Source-ref к изменению понятия сильного простого числа, используемого в криптографии, нестрого говоря, простого числа, для которого <math> p-1 </math> имеет достаточно большие делители. В современных криптосистемах стараютсяШаблон:Source-ref использовать именно сильные простые числа, так как это повышает стойкость используемых алгоритмов и систем в целом.
Определения и математические сведения
Число называется <math>B</math>-Шаблон:IwШаблон:Sfn, если все его простые делители, в степенях, в которых они входят в разложение этого числа <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 году в «Трудах Кембриджеского философского общества»Шаблон:Sfn. Статья посвящена теоретической оценке сложности факторизации большого числа <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.
- Выберем небольшое целое <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 это сделать вычислением <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:
- <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.
Современная версия
Эта переработанная по сравнению с оригинальной версия алгоритма использует понятия Шаблон:Iw и ориентирована на практическое применение. Значительные изменения претерпела первая стадия, в то время, как вторая сохранилась практически без изменений, опять же, с теоретической точки зрения, ничего значительного, по сравнению предыдущей версией, добавлено не было. Именно приведённый ниже алгоритм имеют в виду, когда говорят о «методе Полларда»Шаблон:SfnШаблон:Sfn.
Первая стадия
- Пусть <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, где <math>b = a^{M(B)} \mod N</math>.
- Возможно два случая, в которых приведенный выше алгоритм не даст результатаШаблон:Sfn.
- В случае, когда <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Шаблон:Sfn.
- Вторая стадия алгоритма находит делители <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. Для ускорения работы алгоритма полезно предварительно вычислить все <math>b^{\delta_i}, \forall \delta_i \in \Delta</math>Шаблон:Sfn и при пользоваться уже готовыми значениями.
- Теперь необходимо последовательно вычислять <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.
- Если <math>q^t < B_1</math>, то делитель будет найден на первой стадии алгоритмаШаблон:Sfn.
- В противном случае для успеха алгоритма необходимо, чтобы <math>q^t < B_2</math>, а все остальные делители <math>p-1</math> вида <math>q^r</math> были меньше <math>B_1</math>Шаблон:Sfn.
Модификации и улучшения
- Позднее сам Поллард высказал мнение о возможности ускорения алгоритма с использованием быстрого преобразования ФурьеШаблон:Sfn во второй стадии, однако он не привел реальных способов, как сделать этоШаблон:Sfn.
- Ещё позже, в 1990 году это сделали математики Питер Монтгомери (Peter Montgomery) и Роберт Силверман (Robert Silverman)Шаблон:Sfn. Авторам удалось добиться увеличения скорости исполнения второй стадии алгоритма.
Оценка эффективности
- Сложность первой стадии оценивается как <math>O(B \cdot \ln B \cdot (\ln N)^2 + (\ln N)^3)</math>, оставляя только слагаемое высшего порядка получаем оценку первой стадии алгоритмаШаблон:Sfn <math>O(B \cdot \ln B \cdot (\ln N)^2)</math>.
- Согласно оценке Монтгомери, сложность второй стадии, с точностью до слагаемых наивысшего порядка составляет <math>O(\pi (B_2))</math>Шаблон:SfnШаблон:Sfn, где <math>\pi (s)</math> — число простых чисел, меньших <math>s</math>. Оценка Чебышева дает приближённое равенство <math>\pi (s) \approx \frac{s}{\ln s}</math>.
Рекорды
На данный момент (10.10.2016) три самых больших простых делителя, найденных методом P-1, состоят из 66, 64 и 59 десятичных цифр[1].
| Кол-во цифр | p | Делитель числа | Кем найден | Когда найден | B | B2 |
|---|---|---|---|---|---|---|
| 66 | 672038771836751227845696565342450315062141551559473564642434674541
|
<math>960^{119}-1</math> | Т. Ногара | 29.06.2006 | <math>10^8</math> | <math>10^{10}</math> |
| 64 | 1939611922516629203444058938928521328695726603873690611596368359
|
<math>10^{243}-4\cdot10^{121}-1</math> | М. Тервурен | 13.09.2012 | <math>10^{9}</math> | <math>10^{13}</math> |
| 59 | 12798830540286697738097001413455268308836003073182603569933
|
<math>8069000260399979023963141^{17}-1</math> | A. Круппа | 30.06.2011 | <math>10^9</math> | <math>10^{10}</math> |
Применения
- GMP-ECM[2] — пакет включает в себя эффективное применение <math>p-1</math>-метода.
- Prime95 и MPrime — официальные клиенты GIMPS — используют метод, чтобы отсеять кандидатов.
См. также
Примечания
Литература
