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

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

P-1 метод Полларда (читается как п-1 метод Полларда) — один из методов факторизации целых чисел.

Метод был впервые опубликован британским математиком Джоном М. Поллардом в 1974 году в статье журнала Математические Труды Кэмбриджеского Философского Общества[1]. Алгоритм имеет ограниченную применимость, то есть не всегда дает результат, в частности, он не приведет к успеху, если наименьший из делителей числа  n , искомое  p — сильное простое число[1][2].

Исторически, именно появление данного алгоритма привело[3] к изменению понятия сильного простого числа, используемого в криптографии, нестрого говоря, простого числа, для которого  p-1 имеет достаточно большие делители. В современных криптосистемах стараются[3] использовать именно сильные простые числа, так как это повышает стойкость используемых алгоритмов и систем в целом.

Определения и математические сведения[править | править исходный текст]

  • Определение: Число называется гладким степени B, если все его простые делители, в степенях, в которых они входят в разложение этого числа, меньше  B .
  • Согласно малой теореме Ферма для любого простого числа ~ p и для любого целого числа ~ a, такого что ~a и ~ p взаимно просты, или, что в данном случае равносильно, ~ p не делит ~ a , справедливо:
~a^{(p-1)} \equiv 1 \mod p , более того ~ \forall M=(p-1)l, l \in N \Rightarrow a^M \equiv 1 \mod p .

Оригинальный алгоритм (1974 год)[править | править исходный текст]

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

Первая стадия[править | править исходный текст]

  1. Задача состоит в том, чтобы найти делитель числа ~N отличный от единицы. Прежде всего необходимо выбрать 2 числа ~L, M,, такие, что  1<L<M<\sqrt{N}, M<L^2 .
  2. Вычислим теперь число ~P = \prod_{k=1}^{m} p_k^{c_k}, где ~p_k — все простые числа меньшие ~L . Здесь допускается некоторая свобода в выборе ~c_k, однако точно известно, что для маленьких ~p_k, ~c_k должно быть больше единицы[1].
  3. Выберем небольшое целое a>1 и вычислим
~b = a^P \mod N
 C = (b-1, N) если C \ne 1 мы нашли делитель  N , в противном случае переходим ко второй стадии.

Вторая стадия[править | править исходный текст]

  • На этом шаге необходимо вычислить последовательность
 F_m \equiv b^{m-1} - 1 \mod N где ~m — простое, ~L < m < M , надеясь, что на каком-нибудь шаге получится
 g_m = (F_m, N) > 1
  • Легче всего[1] это сделать вычислением ~b^m для каждого нечётного ~m домножением на ~b^2, беря ~G_i = (b^i,N) через равные промежутки. Если ~ 1 < G_i < N делитель найден. Если же ~G_i = N, G_{i-1} = 1 , то необходимо точнее исследовать этот участок.

Замечание[править | править исходный текст]

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

~ p-1 = A или ~ p-1 = Aq , где ~A является L-гладким, а q — простое, такое что L<q<M[1].

Современная версия[править | править исходный текст]

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

Первая стадия[править | править исходный текст]

  1. Пусть ~n гладкое степени ~B , и требуется найти делитель числа ~n. В первую очередь вычисляется число ~ M(B) = \prod_i p_i^{k_i} где произведение ведётся по всем простым ~p_i в максимальных степенях ~ k_i: p_i^{k_i}<B
  2. Тогда искомый делитель ~q = (a^{M(B)} - 1, n) [4].

Пример[править | править исходный текст]

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

Замечания[править | править исходный текст]

  • При больших ~B число ~M(B) может оказаться весьма большим, сравнимым по значению с ~B!, в таких случаях может оказаться целесообразно разбить ~M(B) на множители приблизительно одинаковой величины ~M(B) = \prod_i M_i и вычислять последовательность
~ a_1 = a^{M_1} \mod n;
~ a_{k+1} = a_k^{M_{k+1}} \mod n.
  • Возможно два случая, в которых приведенный выше алгоритм не даст результата[5].
  1. В случае, когда ~(a^{M(B)} - 1, n) = n точно можно сказать, что у ~n есть делитель, являющийся гладким степени ~B и проблему должен решить иной выбор ~a.
  2. В более частом случае, когда ~(a^{M(B)} - 1, n) = 1 стоит перейти ко второй стадии алгоритма, которая значительно повышает вероятность результата, хотя и не гарантирует его.

Вторая стадия[править | править исходный текст]

  • Прежде всего необходимо зафиксировать границы ~B_1 = B, B_2 \gg B, обычно ~B_2 \leq B^2[5][4].
  • Вторая стадия алгоритма находит делители ~ n, такие что ~ p-1 = q \cdot f, где ~ f — гладкое степени ~B, а ~q простое, такое что ~B_1<q<B_2 .
  1. Для дальнейшего нам потребуется вектор из простых чисел ~q_i от ~B_1 до ~B_2, из которого легко получить вектор разностей между этими простыми числами ~ D = (D_1,D_2, ... ), D_i = q_{i+1} - q_i, причем ~D_i — относительно небольшие числа, и ~D_i \in \Delta, где ~\Delta — конечно множество [4]. Для ускорения работы алгоритма полезно предварительно вычислить все ~b^{\delta_i}, \forall \delta_i \in \Delta[4] и при пользоваться уже готовыми значениями.
  2. Теперь необходимо последовательно вычислять ~ c_0 = b \mod n, c_i = c_{i-1}^{\delta_i} \mod n, где ~ b = a^M(B_1) \mod n, вычисленное в первой стадии, на каждом шаге считая ~Q = (c_i-1, n). Как только ~Q \neq 1 , можно прекращать вычисления.

Условия сходимости[править | править исходный текст]

  • Если ~n является произведением двух сильных простых чисел ~p,q, причем ~q<p, q>2B+1, то ~(\rho-1)-алгоритм Полларда не факторизует ~n[2].
  • Пусть ~p наименьший делитель ~n, ~q^t = max(q_i^{t_i}) максимум берется по всем степеням ~q_i^{t_i}, делящим ~p-1[4].
    • Если ~q^t < B_1, то делитель будет найден на первой стадии алгоритма[4].
    • В противном случае для успеха алгоритма необходимо, чтобы ~q^t < B_2, а все остальные делители ~p-1 вида ~q^r были меньше ~B_1[4].

Модификации и улучшения[править | править исходный текст]

  • Позднее сам Поллард высказал мнение о возможности ускорения алгоритма с использованием быстрого преобразования Фурье[4] во второй стадии, однако он не привел реальных способов, как сделать это[6].
  • Ещё позже, в [1990] году это сделали математики Питер Монтгомери (Peter Montgomery) и Роберт Силверман (Robert Silverman)[6]. Авторам удалось добиться скорости исполнения алгоритма второй стадии алгоритма ~ O(k \ln(n)( \lg (k)+ \lg (n)) [6].

Оценка эффективности[править | править исходный текст]

  • Сложность первой стадии оценивается как ~O(B \cdot \ln B \cdot (\ln n)^2 + (\ln n)^3), оставляя только слагаемое высшего порядка получаем оценку первой стадии алгоритма[4] ~O(B \cdot \ln B \cdot (\ln n)^2).
  • Согласно оценке Монтгомери, сложность второй стадии, с точностью до слагаемых наивысшего порядка составляет ~O(\pi (B_2))[1][4] , где ~\pi (s), s\in \Z[4] — число простых чисел, меньших ~s. оценка Чебышева дает приближённое равенство ~\pi (s) \approx \frac{s}{\ln s}.

Рекорды[править | править исходный текст]

На данный момент (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 используют метод, чтобы отсеять кандидатов.

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

Литература[править | править исходный текст]