P-1 метод Полларда (читается^{[источник не указан 185 дней]} как ро-1 метод Полларда) — один из методов факторизации целых чисел.

Метод был впервые опубликован британским математиком Джоном М. Поллардом в 1974 году в статье журнала Математические Труды Кэмбриджеского Философского Общества^[1]. Алгоритм имеет ограниченную применимость, то есть не всегда дает результат, в частности, он не приведет к успеху, если наименьший из делителей числа , искомое  — сильное простое число^[1][2].

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

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

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

, более того .

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

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

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

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

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

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

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

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

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

Замечание

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

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

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

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

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

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

Пример

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

Замечания

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

.

• Возможно два случая, в которых приведенный выше алгоритм не даст результата^[5].

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

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

• Прежде всего необходимо зафиксировать границы , обычно ^[5][4].
• Вторая стадия алгоритма находит делители , такие что , где  — гладкое степени , а простое, такое что .

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

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

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

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

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

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

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

Рекорды

На данный момент (09.12.2008) три самых больших простых делителя^[7], найденных методом P-1, состоят из 66, 58 и 57 десятичных цифр.

Применения

• GMP-ECM (англ.) — Пакет включает в себя эффективное применение P-1 метода.
• Prime95 (англ.) и MPrime (англ.) — официальные клиенты GIMPS используют метод, чтобы отсеять кандидатов.

См. также

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

Примечания