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

1. Задача состоит в том, чтобы найти собственный делитель числа ${\displaystyle N}$ отличный от единицы. Прежде всего необходимо выбрать два числа ${\displaystyle B,M,}$ такие, что ${\displaystyle 1<B<M<{\sqrt {N}},M<B^{2}}$.
2. Вычислим теперь число ${\displaystyle M(B)=\prod _{k=1}^{m}p_{k}^{c_{k}}}$, где ${\displaystyle p_{k}}$ — все простые числа меньшие ${\displaystyle B}$. Здесь допускается некоторая свобода в выборе ${\displaystyle c_{k}}$, однако точно известно, что для маленьких ${\displaystyle p_{k}}$, ${\displaystyle c_{k}}$ должно быть больше единицы[1].
3. Выберем небольшое целое ${\displaystyle a>1}$ и вычислим

${\displaystyle b=a^{M(B)}\mod N}$

${\displaystyle q=(b-1,N)}$ если ${\displaystyle q\neq 1}$ мы нашли делитель ${\displaystyle N}$, в противном случае переходим ко второй стадии.

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

${\displaystyle F_{m}\equiv b^{m-1}-1\mod N,}$ где ${\displaystyle m}$ — простое, ${\displaystyle B<m<M}$, надеясь, что на каком-нибудь шаге получится

${\displaystyle g_{m}=(F_{m},N)>1}$

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

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

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

1. Пусть ${\displaystyle N}$ ${\displaystyle B}$-гладкостепенное, и требуется найти делитель числа ${\displaystyle N}$. В первую очередь вычисляется число ${\displaystyle M(B)=\prod _{i}p_{i}^{k_{i}}}$ где произведение ведётся по всем простым ${\displaystyle p_{i}}$ в максимальных степенях ${\displaystyle k_{i}:p_{i}^{k_{i}}<B}$
2. Тогда искомый делитель ${\displaystyle q=(b-1,N)}$[4], где ${\displaystyle b=a^{M(B)}\mod N}$.

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

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

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

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

${\displaystyle a_{1}=a^{M_{1}}\mod N;}$

${\displaystyle a_{k+1}=a_{k}^{M_{k+1}}\mod N}$.

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

1. Для дальнейшего нам потребуется вектор из простых чисел ${\displaystyle q_{i}}$ от ${\displaystyle B_{1}}$ до ${\displaystyle B_{2}}$, из которого легко получить вектор разностей между этими простыми числами ${\displaystyle D=(D_{1},D_{2},...),D_{i}=q_{i+1}-q_{i}}$, причём ${\displaystyle D_{i}}$ — относительно небольшие числа, и ${\displaystyle D_{i}\in \Delta }$, где ${\displaystyle \Delta }$ — конечно множество[4]. Для ускорения работы алгоритма полезно предварительно вычислить все ${\displaystyle b^{\delta _{i}},\forall \delta _{i}\in \Delta }$[4] и при пользоваться уже готовыми значениями.
2. Теперь необходимо последовательно вычислять ${\displaystyle c_{0}=b_{1}\mod N,c_{i}=c_{i-1}^{\delta _{i}}\mod N}$, где ${\displaystyle b_{1}=a^{M(B_{1})}\mod N}$, вычисленное в первой стадии, на каждом шаге считая ${\displaystyle G=(c_{i}-1,N)}$. Как только ${\displaystyle G\neq 1}$, можно прекращать вычисления.