Факторизация целых чисел

Шаг 1. Начальная установка. Присвоить ${\displaystyle t=0,k=0,n=N}$(В ходе выполнения алгоритма переменные ${\displaystyle t,k,n}$ подчинены следующим условиям: ${\displaystyle n=N/p_{1}...p_{t}}$ и ${\displaystyle n}$ не имеет простых множителей, меньших ${\displaystyle d_{k}}$)

Шаг 2. ${\displaystyle n=1?}$ Если ${\displaystyle n=1}$, алгоритм заканчивается.

Шаг 3. Разделить. Присвоить ${\displaystyle q=\lfloor n/d_{k}\rfloor ,r=n\mod d_{k}.}$ (Здесь ${\displaystyle q}$ и ${\displaystyle r}$ соответственно частное и остаток от деления числа ${\displaystyle n}$ на ${\displaystyle d_{k}}$.)

Шаг 4. Остаток равен нулю? Если ${\displaystyle r\neq 0}$, то перейти к шагу 6.

Шаг 5. Множитель найден. Увеличить ${\displaystyle t}$ на ${\displaystyle 1}$ и присвоить ${\displaystyle p_{t}=d_{k},n=q}$. Возвратиться к шагу 2.

Шаг 6. Частное мало? Если ${\displaystyle q>d_{k}}$, увеличить ${\displaystyle k}$ на 1 и возвратиться к шагу 3.

Шаг 7. n — простое число. Увеличить ${\displaystyle t}$ на ${\displaystyle 1}$, присвоить ${\displaystyle p_{t}=n}$ и завершить выполнение алгоритма.

Шаг 1. Начальная установка. Присвоить ${\displaystyle x=2\lfloor {\sqrt {N}}\rfloor +1,y=1,r=\lfloor {\sqrt {N}}\rfloor ^{2}-N.}$ (Во время выполнения этого алгоритма величины x, y, r отвечают соответственно величинам ${\displaystyle 2x+1,2y+1,x^{2}-y^{2}-N}$ в уравнении ${\displaystyle N=uv=x^{2}-y^{2}(x={\dfrac {u+v}{2}},y={\dfrac {u-v}{2}})}$. Должно соблюдаться условие ${\displaystyle |r|<x,y<x}$.)

Шаг 2. Выполнено? Если ${\displaystyle r=0}$, то выполнение алгоритма завершается. Имеем

${\displaystyle N={\frac {x-y}{2}}\cdot {\frac {x+y-2}{2}}}$

Шаг 3. Шаг по x. Присвоить ${\displaystyle r=r+x}$ и ${\displaystyle x=x+2}$.

Шаг 4. Шаг по y. Присвоить ${\displaystyle r=r-y}$ и ${\displaystyle y=y+2}$.

Шаг 5. Проверить r. Если ${\displaystyle r>0}$, то возвратиться к шагу 4, иначе возвратиться к шагу 2.

Шаг 1. Выбираем небольшое число ${\displaystyle x_{0}}$ и строим последовательность чисел ${\displaystyle {x_{k}},k=0,1,2,...,}$ определяя каждое следующее ${\displaystyle x_{k+1}}$ по формуле: ${\displaystyle x_{k+1}=x_{k}^{2}-1\mod n}$

Шаг 2. Одновременно на каждом шаге ${\displaystyle i}$ вычисляем Н.О.Д ${\displaystyle d}$ числа ${\displaystyle n}$ и всевозможных разностей ${\displaystyle |x_{i}-x_{j}|}$, где ${\displaystyle j<i}$.

Шаг 3. Когда будет найден ${\displaystyle d=\gcd(n,|x_{i}-x_{j}|)}$, отличный от ${\displaystyle 1}$, вычисление заканчивается. Найденное ${\displaystyle d}$ является делителем ${\displaystyle n}$. Если ${\displaystyle n/d}$ не является простым числом, то процедуру можно продолжить, взяв вместо ${\displaystyle n}$ число ${\displaystyle n/d}$.

Пусть ${\displaystyle r,s,n}$ — натуральные числа, удовлетворяющие условиям ${\displaystyle 1\leq r<s<n;\;n^{1/3}<s;\;\gcd(r,s)=1}$

Шаг 1. С помощью обобщённого алгоритма Евклида найти ${\displaystyle r^{*}\in \mathbb {N} ,rr^{*}\equiv 1\mod s}$. Найти ${\displaystyle r'}$ такое, что ${\displaystyle r'\equiv r^{*}n\mod s,0\leq r'<s}$.

Шаг 2. Для очередного значения ${\displaystyle i=0,1,2,...}$ найти числа ${\displaystyle a_{i},b_{i},c_{i}}$ по следующим правилам:

${\displaystyle a_{0}=s,\;b_{0}=0,\;c_{0}=0}$ ${\displaystyle a_{1}=rr'\mod s,0<a_{1}\leq s,\;b_{1}=1,\;c_{1}\equiv {\frac {n-rr'}{s}}r^{*}(\mod s)}$

при ${\displaystyle i\geq 2}$:

${\displaystyle a_{i}=a_{i-2}-q_{i}a_{i-1},\;\;b_{i}=b_{i-2}-q_{i}b_{i-1},\;\;c_{i}=c_{i-2}-q_{i}c_{i-1}(\mod s)}$

${\displaystyle q_{i}}$ — частное от деления ${\displaystyle a_{i-2}}$ на ${\displaystyle a_{i-1}}$, за исключением случая, когда ${\displaystyle i}$ нечётно и остаток от деления равен нулю.

Шаг 3. Для очередного выбора ${\displaystyle a_{i},b_{i},c_{i}}$ найти все целые числа ${\displaystyle c}$, удовлетворяющие условиям

${\displaystyle c=c_{i}\mod s}$,

${\displaystyle |c|<s,\;\;\;\;\;\;}$ если ${\displaystyle i}$ четное,

${\displaystyle 2a_{i}b_{i}\leq c\leq {\frac {n}{s^{2}}}+a_{i}b_{i},\;\;}$ если ${\displaystyle i}$ нечетное.

Шаг 4. Для каждого c из шага 3 решить в целых числах систему уравнений

${\displaystyle \left\{{\begin{array}{rcl}xa_{i}+yb_{i}\;\;\;\;\;\;&=&c\\(xs+r)(ys+r')&=&n\\\end{array}}\right.}$

Если ${\displaystyle x}$ и ${\displaystyle y}$ окажутся неотрицательными целыми числами, то добавить ${\displaystyle xs+r}$

Шаг 5. Если ${\displaystyle a_{i}=0}$, то алгоритм заканчивает работу. Иначе, возвращаемся на шаг 2 к следующему значению ${\displaystyle i}$.

Теорема. Пусть ${\displaystyle z\in \mathbb {N} ,y=z^{2}}$. Тогда для любого натурального числа ${\displaystyle t}$ наименьший простой делитель числа ${\displaystyle \gcd(n,y!)}$ может быть найден за ${\displaystyle O(z\log ^{2}z\log ^{2}t)}$ арифметических операций.

Алгоритм. Положим ${\displaystyle z=[n^{1/4}]+1,y=z^{2}>n^{1/2},t=n}$. Далее с помощью алгоритма теоремы найдём наименьший простой делитель числа ${\displaystyle \gcd(n,y!)}$. Поскольку ${\displaystyle y!}$ делится на наименьший простой делитель ${\displaystyle p}$ числа ${\displaystyle n(p\leq n^{1/2}<y)}$, то алгоритм выдаст именно это число ${\displaystyle p}$.

Сложность первой стадии. ${\displaystyle O(B_{1}\log B_{1}\log ^{2}N)}$, где ${\displaystyle B_{1}}$ — граница[22]

Сложность второй стадии. ${\displaystyle O(\log ^{2}B_{2})+O(\log q_{\pi (B_{1})})+2(\pi (B_{2})-\pi (B_{1}))}$, где ${\displaystyle B_{2}}$ — новая граница. ${\displaystyle B_{2}>>B_{1}}$[23]

Шаг 1. Для всех ${\displaystyle p}$ от ${\displaystyle 2}$ до ${\displaystyle \lceil {\sqrt[{3}]{m}}\rceil }$ выполнять:

Если ${\displaystyle m\equiv 0\mod p}$, то вернуть ${\displaystyle p}$ в качестве делителя числа m и завершить алгоритм.

Шаг 2. Для всех ${\displaystyle b}$ от ${\displaystyle 1}$ до ${\displaystyle \lceil {\sqrt[{3}]{m}}\rceil }$ выполнять:

Шаг 2.1 Определить ${\displaystyle k=0}$ и ${\displaystyle D=\left\lfloor {\frac {\sqrt[{6}]{m}}{4{\sqrt {b}}}}\right\rfloor +1}$

Шаг 2.2 Определить ${\displaystyle x=\lfloor {\sqrt {4bm}}\rfloor +k}$ и ${\displaystyle v=x^{2}-4bm}$

Шаг 2.3 Если ${\displaystyle v}$ является полным квадратом, то определить ${\displaystyle p=\gcd(m,x\pm v)}$ и завершить алгоритм.

Шаг 2.4 Определить ${\displaystyle k=k+1}$.

Шаг 2.5 Если ${\displaystyle k\geq D}$, то вычислить новое значение ${\displaystyle d}$, в противном случае вернуться на шаг 2.2

Шаг 3. Запустить алгоритм с уведомлением, что факторизуемое число ${\displaystyle m}$ — простое.

Шаг 1. Выбрать случайное ${\displaystyle b,1<b<n}$, и вычислить ${\displaystyle b^{2}\mod m}$.

Шаг 2. Пробными делениями попытаться разложить ${\displaystyle b^{2}\mod m}$ на простые множители из факторной базы.

Шаг 3. Если ${\displaystyle b}$ является ${\displaystyle B}$-числом, т.е. ${\displaystyle b^{2}\mod n=\prod \limits _{p\in B}p^{\alpha _{p}(b)}}$ , то запомнить ${\displaystyle {\vec {\alpha }}(b)}$ и ${\displaystyle {\vec {\varepsilon }}(b)}$. Повторять процедуру генерации чисел ${\displaystyle b}$ до тех пор, пока не будет найдено ${\displaystyle m=h+1}$ ${\displaystyle B}$-чисел ${\displaystyle b_{1},...,b_{m}}$.

Шаг 4. Найти (например, решая с помощью алгоритма последовательного исключения неизвестных Гаусса однородную систему линейных уравнений ${\displaystyle x_{1}{\vec {\varepsilon }}(b_{1})\oplus ...\oplus x_{m}{\vec {\varepsilon }}(b_{m})={\vec {0}}}$ относительно неизвестных ${\displaystyle (x_{1},...,x_{m})}$) соотношение линейной зависимости

${\displaystyle {\vec {\varepsilon }}(b_{i_{1}})\oplus ...\oplus {\vec {\varepsilon }}(b_{i_{t}})={\vec {0}},\;\;\;\;\;\;1<t\leq m.}$

Положить

${\displaystyle x=b_{i_{1}}...b_{i_{t}},\;\;\;\;\;\;y=\prod \limits _{p\in B}p^{{\frac {1}{2}}({\vec {\alpha _{p}}}(b_{i_{1}})+...+{\vec {\alpha _{p}}}(b_{i_{t}}))}}$

Шаг 5. Проверить ${\displaystyle x\equiv \pm y(\mod n)}$. Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение

${\displaystyle n=u\cdot v,\;\;\;\;\;\;u=(x+y,n),\;\;\;\;\;\;v=(x-y,n)}$.

На вход алгоритма поступает число ${\displaystyle n}$, которое необходимо факторизовать, параметры ${\displaystyle v,w\in \mathbb {N} }$, зависящие от ${\displaystyle n}$, кроме того, задаются ${\displaystyle a,x,y\in \mathbb {Z} /n\mathbb {Z} }$ такие, что ${\displaystyle P=(x:y:1)\in \mathbb {V} _{n}}$ и для ${\displaystyle b\equiv y^{2}-x^{3}-ax\mod n}$ выполнено условие ${\displaystyle 6(4a^{3}+27b^{2})\in (\mathbb {Z} /n\mathbb {Z} )^{*}}$. Алгоритм находит натуральный делитель ${\displaystyle d}$ числа ${\displaystyle n,1<d<n}$.

Для каждого ${\displaystyle r\in \mathbb {N} ,2\leq r\leq w}$, полагается

${\displaystyle e(r)=max\{m|m\in Z_{\geq 0},r^{m}\leq v+2{\sqrt {v}}+1\}}$

А также

${\displaystyle k=\prod \limits _{2\leq r\leq w}r^{e(r)}}$, ${\displaystyle r}$ — простые.

Пусть ${\displaystyle P=(x:y:1\in \mathbb {V} _{n})}$. Тогда ${\displaystyle P}$ лежит на эллиптической кривой ${\displaystyle E_{a,b}}$ над ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$, определённой уравнением ${\displaystyle Y^{2}=X^{3}+aX+b}$. Необходимо вычислить точку ${\displaystyle kP}$ по правилам арифметики над эллиптическими кривыми. Если в ходе вычисления найден делитель ${\displaystyle d}$ числа ${\displaystyle n}$, то ${\displaystyle n}$ разложилось на множители. Если найден ${\displaystyle kP}$, а делитель ${\displaystyle d}$ не найден, то алгоритм завершает работу и выдаёт сообщение о неудачной попытке факторизации.