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

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

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

Пример модификации алгоритма

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

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

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

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

при $i\geq 2$:

$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)$

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

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

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

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

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

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

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

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

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

Литература

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии — М.: МЦНМО, 2003. — 328 с. — ISBN 978-5-94057-103-2