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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

P-1 метод Полларда (читается как п-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 десятичных цифр.

Кол-во цифр p, p-1 Делитель числа Найден (кем) Найден (когда) B B2
66 672038771836751227845696565342450315062141551559473564642434674541 2².3.5.7.17.23.31.163.401.617.4271.13681.22877.43397.203459.1396027.6995393.13456591.2110402817 960^119-1 T. Nohara 29.06.2006 10^8 10^10
58 1372098406910139347411473978297737029649599583843164650153 2³.3².1049.1627.139999.1284223.7475317.341342347.2456044907.9909876848747 2^2098+1 P. Zimmermann 28.09.2005 10^10 10^13
57 357561419933316305231935975632510092006707198190314688497 2^4.3².11.31.612.2131.7703.102199.12170281.294393133.346193663.940452192083 6^396+1 P. Zimmermann 31.10.2003 10^9 10^12

Применения[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]