WikiSort.ru - Не сортированное

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

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 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}$ , можно прекращать вычисления.