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

-метод Полларда — один из методов факторизации целых чисел.

Впервые опубликован британским математиком Джоном Поллардом[англ.] в 1974 году[1]. Именно появление данного алгоритма привело[2] к изменению понятия сильного простого числа, используемого в криптографии, нестрого говоря, простого числа, для которого имеет достаточно большие делители. В современных криптосистемах стараются[2] использовать именно сильные простые числа, так как это повышает стойкость используемых алгоритмов и систем в целом.

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

Число называется -гладкостепенным[англ.][3], если все его простые делители, в степенях, в которых они входят в разложение этого числа , удовлетворяют . Согласно малой теореме Ферма для любого простого числа и для любого целого числа , такого что и взаимно просты, или, что в данном случае равносильно, не делит , справедливо:

, более того .

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

Джон Поллард впервые опубликовал описанный ниже алгоритм в своей статье «Методы факторизации и проверка простоты» («Theorems of Factorization and Primality Testing») в 1974 году в «Трудах Кембриджеского философского общества»[1]. Статья посвящена теоретической оценке сложности факторизации большого числа или же, в случае простого , проверке его на простоту. Нижеприведённый алгоритм явился следствием и иллюстрацией теоретических выкладок Полларда.

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

  1. Задача состоит в том, чтобы найти собственный делитель числа отличный от единицы. Прежде всего необходимо выбрать два числа такие, что .
  2. Вычислим теперь число , где — все простые числа меньшие . Здесь допускается некоторая свобода в выборе , однако точно известно, что для маленьких , должно быть больше единицы[1].
  3. Выберем небольшое целое и вычислим
если мы нашли делитель , в противном случае переходим ко второй стадии.

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

  • На этом шаге необходимо вычислить последовательность
где — простое, , надеясь, что на каком-нибудь шаге получится
  • Легче всего[1] это сделать вычислением для каждого нечётного домножением на , беря через равные промежутки. Если делитель найден. Если же , то необходимо точнее исследовать этот участок.

Замечание

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

или , где является -гладкостепенным, а — простое, такое что [1].

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

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

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

  1. Пусть -гладкостепенное, и требуется найти делитель числа . В первую очередь вычисляется число где произведение ведётся по всем простым в максимальных степенях
  2. Тогда искомый делитель [4], где .
  • Возможно два случая, в которых приведенный выше алгоритм не даст результата[5].
  1. В случае, когда точно можно сказать, что у есть делитель, являющийся -гладкостепенным и проблему должен решить иной выбор .
  2. В более частом случае, когда стоит перейти ко второй стадии алгоритма, которая значительно повышает вероятность результата, хотя и не гарантирует его.

Пример

Пусть выберем , тогда , возьмём и вычислим теперь , и наконец .

Замечания

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

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

  • Прежде всего необходимо зафиксировать границы , обычно [5][4].
  • Вторая стадия алгоритма находит делители , такие что , где -гладкостепенное, а простое, такое что .
  1. Для дальнейшего нам потребуется вектор из простых чисел от до , из которого легко получить вектор разностей между этими простыми числами , причём — относительно небольшие числа, и , где — конечно множество[4]. Для ускорения работы алгоритма полезно предварительно вычислить все [4] и при пользоваться уже готовыми значениями.
  2. Теперь необходимо последовательно вычислять , где , вычисленное в первой стадии, на каждом шаге считая . Как только , можно прекращать вычисления.

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

  • Пусть наименьший делитель , максимум берется по всем степеням , делящим [4].
    • Если , то делитель будет найден на первой стадии алгоритма[4].
    • В противном случае для успеха алгоритма необходимо, чтобы , а все остальные делители вида были меньше [4].

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

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

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

  • Сложность первой стадии оценивается как , оставляя только слагаемое высшего порядка получаем оценку первой стадии алгоритма[4] .
  • Согласно оценке Монтгомери, сложность второй стадии, с точностью до слагаемых наивысшего порядка составляет [1][4], где — число простых чисел, меньших . Оценка Чебышева дает приближённое равенство .

Рекорды

На данный момент (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
Т. Ногара 29.06.2006
64 1939611922516629203444058938928521328695726603873690611596368359
= 2 · 3 · 11 · 1187 · 9233729 · 13761367 · 43294577 · 51593573 · 100760321 · 379192511 · 2282985164293 + 1
М. Тервурен 13.09.2012
59 12798830540286697738097001413455268308836003073182603569933
= 22 · 17 · 59 · 107 · 113 · 20414117 · 223034797 · 269477639 · 439758239 · 481458247 · 1015660517 + 1
A. Круппа 30.06.2011

Применения

  • GMP-ECM[8] — пакет включает в себя эффективное применение -метода.
  • Prime95 и MPrime — официальные клиенты GIMPS — используют метод, чтобы отсеять кандидатов.

См. также

Примечания

  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 года.

Литература