P-1 метод Полларда — алгоритм разложения натурального числа на простые множители. Предложен Джоном Поллардом в 1974 году. Алгоритм предназначен для нахождения простых делителей , у которых хорошо раскладывается на множители, то есть имеет небольшой максимальный простой делитель. Если обозначить этот максимальный простой делитель , то алгоритм требует действий. Метод очень быстро находит простые факторы малой и средней величины (до 20-25 десятичных цифр). Актуальным рекордом для P-1 метода является простой делитель числа , состоящий из 66 десятичных цифр, установленный T. Nohara 29.06.2006.

Первоначальная версия алгоритма

«Шаг 1»

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

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

Согласно малой теореме Ферма в группе справедливо , что равносильно НОД. Заметим, что . Если граница выбрана удачно, скорее всего НОД будет равен . В некоторых случаях можно получить НОД равным . Это означает, что метод нашёл сразу все делители. В этом случае надо просто уменьшить значение . Также заметим, что так как может быть достаточно большим числом, то все вычисления производятся по модулю .

Если НОД, это означает, что алгоритм завершился неудачно и имеет делители большие чем . Возможным планом действий могут быть:

• Увеличить значение (в этом случае не стоит начинать алгоритм заново. Можно пересмотреть значение согласно новой границе ).
• Применить метод для другого (алгоритм надо начать заново. Надежда найти простой делитель основывается на том, что новое может быть большой степенью порождающего элемента в ).
• Использовать другой метод факторизации (например P+1 или метод эллиптических кривых)
• Перейти к «шагу 2» алгоритма

«Шаг 2»

Если «шаг 1» завершился неудачно, значит . Но может быть, что для некоторого простого числа .

Обозначим , тогда или опять же НОД. Таким образом, можно рассмотреть все простые числа между и и для каждого высчитать . Однако, это не очень эффективно.

Более эффективными может быть следующие выполнение «шага 2»:

Рассмотрим все простые числа между и . Пусть обозначает j-ое простое число. Так как разница между двумя соседними простыми числами заведомо мала (не более чем ), то мы можем сохранить в таблице значения , где . Далее, мы можем вычислить последовательно для всех в указанных выше границах значения .

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

Peter L. Montgomery предложил другие более эффективные варианты «шага 2».

Рекорды

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

Примечания