p−1-метод Полларда

p − 1 {displaystyle p-1} -метод Полларда — один из методов факторизации целых чисел.

Впервые опубликован британским математиком Джоном Поллардом в 1974 году. Именно появление данного алгоритма привело к изменению понятия сильного простого числа, используемого в криптографии, нестрого говоря, простого числа, для которого p − 1 {displaystyle p-1} имеет достаточно большие делители. В современных криптосистемах стараются использовать именно сильные простые числа, так как это повышает стойкость используемых алгоритмов и систем в целом.

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

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

a ( p − 1 ) ≡ 1 mod p {displaystyle a^{(p-1)}equiv 1mod p} , более того ∀ M = ( p − 1 ) l , l ∈ N ⇒ a M ≡ 1 mod p {displaystyle forall M=(p-1)l,lin NRightarrow a^{M}equiv 1mod p} .

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

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

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

Задача состоит в том, чтобы найти собственный делитель числа N {displaystyle N} отличный от единицы. Прежде всего необходимо выбрать два числа B , M , {displaystyle B,M,} такие, что 1 < B < M < N , M < B 2 {displaystyle 1<B<M<{sqrt {N}},M<B^{2}} .

Вычислим теперь число M ( B ) = ∏ k = 1 m p k c k {displaystyle M(B)=prod _{k=1}^{m}p_{k}^{c_{k}}} , где p k {displaystyle p_{k}} — все простые числа меньшие B {displaystyle B} . Здесь допускается некоторая свобода в выборе c k {displaystyle c_{k}} , однако точно известно, что для маленьких p k {displaystyle p_{k}} , c k {displaystyle c_{k}} должно быть больше единицы.

Выберем небольшое целое a > 1 {displaystyle a>1} и вычислим

b = a M ( B ) mod N {displaystyle b=a^{M(B)}mod N} q = ( b − 1 , N ) {displaystyle q=(b-1,N)} если q ≠ 1 {displaystyle q eq 1} мы нашли делитель N {displaystyle N} , в противном случае переходим ко второй стадии.

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

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

F m ≡ b m − 1 − 1 mod N , {displaystyle F_{m}equiv b^{m-1}-1mod N,} где m {displaystyle m} — простое, B < m < M {displaystyle B<m<M} , надеясь, что на каком-нибудь шаге получится g m = ( F m , N ) > 1 {displaystyle g_{m}=(F_{m},N)>1}

• Легче всего это сделать вычислением b m {displaystyle b^{m}} для каждого нечётного m {displaystyle m} домножением на b 2 {displaystyle b^{2}} , беря G i = ( b i , N ) {displaystyle G_{i}=(b^{i},N)} через равные промежутки. Если 1 < G i < N {displaystyle 1<G_{i}<N} делитель найден. Если же G i = N , G i − 1 = 1 {displaystyle G_{i}=N,G_{i-1}=1} , то необходимо точнее исследовать этот участок.

Замечание

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

p − 1 = A {displaystyle p-1=A} или p − 1 = A q {displaystyle p-1=Aq} , где A {displaystyle A} является B {displaystyle B} -гладкостепенным, а q {displaystyle q} — простое, такое что B < q < M {displaystyle B<q<M} .

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

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

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

Пусть N {displaystyle N} B {displaystyle B} -гладкостепенное, и требуется найти делитель числа N {displaystyle N} . В первую очередь вычисляется число M ( B ) = ∏ i p i k i {displaystyle M(B)=prod _{i}p_{i}^{k_{i}}} где произведение ведётся по всем простым p i {displaystyle p_{i}} в максимальных степенях k i : p i k i < B {displaystyle k_{i}:p_{i}^{k_{i}}<B}

Тогда искомый делитель q = ( b − 1 , N ) {displaystyle q=(b-1,N)} , где b = a M ( B ) mod N {displaystyle b=a^{M(B)}mod N} .

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

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

В более частом случае, когда ( b − 1 , N ) = 1 {displaystyle (b-1,N)=1} стоит перейти ко второй стадии алгоритма, которая значительно повышает вероятность результата, хотя и не гарантирует его.

Пример

Пусть N = 10001 {displaystyle N=10001} выберем B = 10 {displaystyle B=10} , тогда M ( B ) = 2 3 ⋅ 3 2 ⋅ 5 ⋅ 7 = 2520 {displaystyle M(B)=2^{3}cdot 3^{2}cdot 5cdot 7=2520} , возьмём a = 2 {displaystyle a=2} и вычислим теперь b = a M ( B ) mod N = 2 2520 mod 10001 = 3578 {displaystyle b=a^{M(B)}mod N=2^{2520}mod 10001=3578} , и наконец ( b − 1 , N ) = ( 3578 − 1 , 10001 ) = 73 {displaystyle (b-1,N)=(3578-1,10001)=73} .

Замечания

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

a 1 = a M 1 mod N ; {displaystyle a_{1}=a^{M_{1}}mod N;} a k + 1 = a k M k + 1 mod N {displaystyle a_{k+1}=a_{k}^{M_{k+1}}mod N} .

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

• Прежде всего необходимо зафиксировать границы B 1 = B , B 2 ≫ B {displaystyle B_{1}=B,B_{2}gg B} , обычно B 2 ≤ B 2 {displaystyle B_{2}leq B^{2}} .
• Вторая стадия алгоритма находит делители N {displaystyle N} , такие что p − 1 = q ⋅ A {displaystyle p-1=qcdot A} , где A {displaystyle A} — B {displaystyle B} -гладкостепенное, а q {displaystyle q} простое, такое что B 1 < q < B 2 {displaystyle B_{1}<q<B_{2}} .

Для дальнейшего нам потребуется вектор из простых чисел q i {displaystyle q_{i}} от B 1 {displaystyle B_{1}} до B 2 {displaystyle B_{2}} , из которого легко получить вектор разностей между этими простыми числами D = ( D 1 , D 2 , . . . ) , D i = q i + 1 − q i {displaystyle D=(D_{1},D_{2},...),D_{i}=q_{i+1}-q_{i}} , причём D i {displaystyle D_{i}} — относительно небольшие числа, и D i ∈ Δ {displaystyle D_{i}in Delta } , где Δ {displaystyle Delta } — конечно множество. Для ускорения работы алгоритма полезно предварительно вычислить все b δ i , ∀ δ i ∈ Δ {displaystyle b^{delta _{i}},forall delta _{i}in Delta } и при пользоваться уже готовыми значениями.

Теперь необходимо последовательно вычислять c 0 = b 1 mod N , c i = c i − 1 δ i mod N {displaystyle c_{0}=b_{1}mod N,c_{i}=c_{i-1}^{delta _{i}}mod N} , где b 1 = a M ( B 1 ) mod N {displaystyle b_{1}=a^{M(B_{1})}mod N} , вычисленное в первой стадии, на каждом шаге считая G = ( c i − 1 , N ) {displaystyle G=(c_{i}-1,N)} . Как только G ≠ 1 {displaystyle G eq 1} , можно прекращать вычисления.

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

• Пусть p {displaystyle p} наименьший делитель N {displaystyle N} , q t = m a x ( q i t i ) {displaystyle q^{t}=max(q_{i}^{t_{i}})} максимум берется по всем степеням q i t i {displaystyle q_{i}^{t_{i}}} , делящим p − 1 {displaystyle p-1} .
  • Если q t < B 1 {displaystyle q^{t}<B_{1}} , то делитель будет найден на первой стадии алгоритма.
  • В противном случае для успеха алгоритма необходимо, чтобы q t < B 2 {displaystyle q^{t}<B_{2}} , а все остальные делители p − 1 {displaystyle p-1} вида q r {displaystyle q^{r}} были меньше B 1 {displaystyle B_{1}} .

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

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

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

• Сложность первой стадии оценивается как O ( B ⋅ ln ⁡ B ⋅ ( ln ⁡ N ) 2 + ( ln ⁡ N ) 3 ) {displaystyle O(Bcdot ln Bcdot (ln N)^{2}+(ln N)^{3})} , оставляя только слагаемое высшего порядка получаем оценку первой стадии алгоритма O ( B ⋅ ln ⁡ B ⋅ ( ln ⁡ N ) 2 ) {displaystyle O(Bcdot ln Bcdot (ln N)^{2})} .
• Согласно оценке Монтгомери, сложность второй стадии, с точностью до слагаемых наивысшего порядка составляет O ( π ( B 2 ) ) {displaystyle O(pi (B_{2}))} , где π ( s ) {displaystyle pi (s)} — число простых чисел, меньших s {displaystyle s} . Оценка Чебышева дает приближённое равенство π ( s ) ≈ s ln ⁡ s {displaystyle pi (s)approx {frac {s}{ln s}}} .

Рекорды

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

Применения

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