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

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

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

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

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

если мы нашли делитель , в противном случае переходим ко второй стадии.

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

где — простое, , надеясь, что на каком-нибудь шаге получится

Легче всего это сделать вычислением для каждого нечётного домножением на , беря через равные промежутки. Если делитель найден. Если же , то необходимо точнее исследовать этот участок.

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

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

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

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

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

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

.

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

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

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

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

Рекорды На данный момент (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 Т. Ногара 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 — пакет включает в себя эффективное применение -метода. Prime95 и MPrime — официальные клиенты GIMPS — используют метод, чтобы отсеять кандидатов.

См. также

P+1-метод Уильямса Ро-алгоритм Полларда

Примечания

Литература

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