Детерминированный алгоритм факторизации Ленстры

Детерминированный алгоритм факторизации Ленстры Сложность ${\displaystyle O(n^{1/3}\log ^{2}n)}$. ^[1]

Следует отметить, что несмотря на относительно неплохую эффективность среди экспоненциальных алгоритмов, в алгоритме Ленстры есть необходимость неоднократно вычислять квадратный корень в одном из шагов алгоритма, что, безусловно, является более трудоёмким, чем сложение или вычитание^[2].

Пример модификации алгоритма^[3]

Пусть ${\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}$.