Processing math: 100%

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

P-1 метод Полларда (читается как п-1 метод Полларда) — одиниз методов факторизации целых чисел.
 Метод был впервые опубликован британским математиком в 1974 году встатье журнала .
 Исторически, именно появление данного алгоритма привело к изменениюпонятия сильного простого числа, используемого в криптографии, нестрогоговоря, простого числа, для которого p1 имеет достаточно большиеделители. В современных криптосистемах стараются использовать именносильные простые числа, так как это повышает стойкость используемыхалгоритмов и систем в целом.

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



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



a(p1)1modp, более тогоM=(p1)l,lNaM1modp.

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


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

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



  1. Задача состоит в том, чтобы найти собственный делитель числа N отличный от единицы. Прежде всего необходимо выбрать два числа B,M, такие, что $1
  2. Вычислим теперь число M(B)=mk=1pckk, где pk — все простые числа меньшие B. Здесь допускается некоторая свобода в выборе ck, однако точно известно, что для маленьких pk, ck должно быть больше единицы.
  3. Выберем небольшое целое a>1 и вычислим



b=aM(B)modN
q=(b1,N) если q1 мы нашли делитель N, в противном случаепереходим ко второй стадии.

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



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



Fmbm11modN где m — простое, B<m<M,надеясь, что на каком-нибудь шаге получится
gm=(Fm,N)>1


  • Легче всего это сделать вычислением bm для каждого нечётного m домножением на b2, беря Gi=(bi,N) через равные промежутки. Если 1<Gi<N делитель найден. Если же Gi=N,Gi1=1, то необходимо точнее исследовать этот участок.

Замечание


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

p1=A или p1=Aq, где A является B-гладкостепенным, аq — простое, такое что $B

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


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

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



  1. Пусть N B-гладкостепенное, и требуется найти делитель числа N. В первую очередь вычисляется число M(B)=ipkii где произведение ведётся по всем простым pi в максимальных степенях $k_i: p_i^{k_i}
  2. Тогда искомый делитель q=(b1,N), где b=aM(B)modN.


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


  1. В случае, когда (b1,N)=N точно можно сказать, что у n есть делитель, являющийся B-гладкостепенным и проблему должен решить иной выбор a.
  2. В более частом случае, когда (b1,N)=1 стоит перейти ко второй стадии алгоритма, которая значительно повышает вероятность результата, хотя и не гарантирует его.


agraphПример
 Пусть N=10001 выберем B=10, тогдаM(B)=233257=2520, возьмём a=2 ивычислим теперь b=aM(B)modN=22520mod10001=3578, инаконец (b1,N)=(35781,10001)=73.

agraphЗамечания

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



a1=aM1modN;



ak+1=aMk+1kmodN.

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



  • Прежде всего необходимо зафиксировать границы B1=B,B2B, обычно B2B2.
  • Вторая стадия алгоритма находит делители N, такие что p1=qA, где A — B-гладкостепенное, а q простое, такое что $B_1

    1. Для дальнейшего нам потребуется вектор из простых чисел qi от B1 до B2, из которого легко получить вектор разностей между этими простыми числами D=(D1,D2,...),Di=qi+1qi, причём Di — относительно небольшие числа, и DiΔ, где Δ — конечно множество. Для ускорения работы алгоритма полезно предварительно вычислить все bδi,δiΔ и при пользоваться уже готовыми значениями.
    2. Теперь необходимо последовательно вычислять c0=b1modN,ci=cδii1modN, где b1=aM(B1)modN, вычисленное в первой стадии, на каждом шаге считая G=(ci1,N). Как только G1, можно прекращать вычисления.

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



    • Пусть p наименьший делитель N, qt=max(qtii) максимум берется по всем степеням qtii, делящим p1.
      • Если qt<B1, то делитель будет найден на первой стадии алгоритма.
      • В противном случае для успеха алгоритма необходимо, чтобы qt<B2, а все остальные делители p1 вида qr были меньше B1.

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



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

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



    • Сложность первой стадии оценивается как O(BlnB(lnN)2+(lnN)3), оставляя только слагаемое высшего порядка получаем оценку первой стадии алгоритма O(BlnB(lnN)2).
    • Согласно оценке Монтгомери, сложность второй стадии, с точностью до слагаемых наивысшего порядка составляет O(π(B2)), где π(s) — число простых чисел, меньших s. Оценка Чебышева дает приближённое равенство π(s)slns.

    Рекорды


     На данный момент (10.10.2016) три самых больших простых делителя,найденных методом P-1, состоят из 66, 64 и 59 десятичных цифр.
    Кол-во цифрpДелитель числаКем найденКогда найденBB2
    66672038771836751227845696565342450315062141551559473564642434674541

     = 2\textsuperscript2 · 3 · 5 · 7 · 17 · 23 · 31 · 163 · 401 · 617 ·4271 · 13681 · 22877 · 43397 · 203459 · 1396027 · 6995393 · 13456591 ·2110402817 + 1
    9601191Т. Ногара29.06.20061081010
    641939611922516629203444058938928521328695726603873690611596368359

     = 2 · 3 · 11 · 1187 · 9233729 · 13761367 · 43294577 · 51593573 ·100760321 · 379192511 · 2282985164293 + 1
    102434101211М. Тервурен13.09.20121091013
    5912798830540286697738097001413455268308836003073182603569933

     = 2\textsuperscript2 · 17 · 59 · 107 · 113 · 20414117 · 223034797 ·269477639 · 439758239 · 481458247 · 1015660517 + 1
    8069000260399979023963141171A. Круппа30.06.20111091010

    Применения



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