- P-1 метод Полларда
-
P-1 метод Полларда (читается как п-1 метод Полларда) — один из методов факторизации целых чисел.
Метод был впервые опубликован британским математиком Джоном М. Поллардом в 1974 году в статье журнала Математические Труды Кэмбриджеского Философского Общества[1]. Алгоритм имеет ограниченную применимость, то есть не всегда дает результат, в частности, он не приведет к успеху, если наименьший из делителей числа , искомое — сильное простое число[1][2].
Исторически, именно появление данного алгоритма привело[3] к изменению понятия сильного простого числа, используемого в криптографии, нестрого говоря, простого числа, для которого имеет достаточно большие делители. В современных криптосистемах стараются[3] использовать именно сильные простые числа, так как это повышает стойкость используемых алгоритмов и систем в целом.
Содержание
Определения и математические сведения
- Определение: Число называется гладким степени , если все его простые делители, в степенях, в которых они входят в разложение этого числа, меньше .
- Согласно малой теореме Ферма для любого простого числа и для любого целого числа , такого что и взаимно просты, или, что в данном случае равносильно, не делит , справедливо:
-
- , более того .
Оригинальный алгоритм (1974 год)
Джон Поллард впервые опубликовал описанный ниже алгоритм в своей статье «Методы факторизации и проверка простоты»(«Theorems of Factorization and Primality Testing») в третьем выпуске журнала Труды Кэмбриджеского Философского Общества[1] за 1974 год. Статья посвящена теоретической оценке сложности факторизации большого числа или же, в случае простого , проверке его на простоту. Нижеприведённый алгоритм явился следствием и иллюстрацией теоретических выкладок Полларда. В связи с чем данная версия имеет скорее теоретическое значение, на практике пользуются современной версией алгоритма, более удобной для реализации[1].
Первая стадия
- Задача состоит в том, чтобы найти делитель числа отличный от единицы. Прежде всего необходимо выбрать 2 числа , такие, что .
- Вычислим теперь число , где — все простые числа меньшие . Здесь допускается некоторая свобода в выборе , однако точно известно, что для маленьких , должно быть больше единицы[1].
- Выберем небольшое целое и вычислим
-
-
- если мы нашли делитель , в противном случае переходим ко второй стадии.
-
Вторая стадия
- На этом шаге необходимо вычислить последовательность
-
- где — простое, , надеясь, что на каком-нибудь шаге получится
- Легче всего[1] это сделать вычислением для каждого нечётного домножением на , беря через равные промежутки. Если делитель найден. Если же , то необходимо точнее исследовать этот участок.
Замечание
С помощью данного метода мы сможем найти только такие простые делители числа , для которых выполнено[1]:
- или , где является -гладким, а — простое, такое что [1].
Современная версия
Эта переработанная по сравнению с оригинальной версия алгоритма использует понятия гладкости и ориентирована на практическое применение. Значительные изменения претерпела первая стадия, в то время, как вторая сохранилась практически без изменений, опять же, с теоретической точки зрения, ничего значительного, по сравнению предыдущей версией, добавлено не было. Именно приведённый ниже алгоритм имеют в виду, когда говорят о «методе Полларда»[4][5].
Первая стадия
- Пусть гладкое степени , и требуется найти делитель числа . В первую очередь вычисляется число где произведение ведётся по всем простым в максимальных степенях
- Тогда искомый делитель [4].
Пример
Пусть выберем , тогда , возьмём и вычислим теперь , и наконец .
Замечания
- При больших число может оказаться весьма большим, сравнимым по значению с , в таких случаях может оказаться целесообразно разбить на множители приблизительно одинаковой величины и вычислять последовательность
-
- .
- Возможно два случая, в которых приведенный выше алгоритм не даст результата[5].
- В случае, когда точно можно сказать, что у есть делитель, являющийся гладким степени и проблему должен решить иной выбор .
- В более частом случае, когда стоит перейти ко второй стадии алгоритма, которая значительно повышает вероятность результата, хотя и не гарантирует его.
Вторая стадия
- Прежде всего необходимо зафиксировать границы , обычно [5][4].
- Вторая стадия алгоритма находит делители , такие что , где — гладкое степени , а простое, такое что .
- Для дальнейшего нам потребуется вектор из простых чисел от до , из которого легко получить вектор разностей между этими простыми числами , причем — относительно небольшие числа, и , где — конечно множество [4]. Для ускорения работы алгоритма полезно предварительно вычислить все [4] и при пользоваться уже готовыми значениями.
- Теперь необходимо последовательно вычислять , где , вычисленное в первой стадии, на каждом шаге считая . Как только , можно прекращать вычисления.
Условия сходимости
- Если является произведением двух сильных простых чисел , причем , то -алгоритм Полларда не факторизует [2].
- Пусть наименьший делитель , максимум берется по всем степеням , делящим [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 используют метод, чтобы отсеять кандидатов.
См. также
Примечания
Литература
- Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: Учебное пособие. — Казань: Казанский Университет, 2011. — С. 53-55. — 190 с.
- Pollard J. M. Методы факторизации и проверка простоты. (англ.) = Theorems on factorization and primality testing. // Математические Труды Кэмбриджского Философского Общества (Mathematical Proceedings of the Cambridge Philosophical Society). — 1974. — Т. 76. — № 3. — С. 521. — DOI:10.1017/S0305004100049252
- Cohen H. A. Курс по Вычислительной Алгебраической Теории Чисел = A Course in Computational Algebraic Number Theory.. — Berlin ; Heildelberg ; New York: Springer, 2000. — С. С. 439. — 550 с. — ISBN 3-54055-640-0
- Montgomery P. L.; Silverman R. D. Продолжение Р-1 алгоритма факторизации с применением БПФ (An FFT extension to the P-1 factoring algorithm) (англ.) // Математика Вычислений (Mathematics of Computation) : журнал. — 1990. — Т. 54. — № 190. — С. 839-854. — DOI:10.1090/S0025-5718-1990-1011444-3
- Karaarslan E. Способы Проверки на Простоту и Важность Простых Чисел в Защищенных Протоколах (англ.) = Primality Testing Techniques and The Importance of Prime Numbers in Security Protocols // Материалы 3й Международной Конференции Математических и Вычислительных Приложений (ICMCA 2002). — Турция, 2002. — С. 1-2.
Эта статья выставлена на рецензию.
Пожалуйста, выскажите своё мнение о ней на подстранице рецензии.Категория:- Алгоритмы факторизации
Wikimedia Foundation. 2010.