Меню Главная Случайная статья Настройки Детерминированный алгоритм факторизации Ленстры Материал из https://ru.wikipedia.org Детерминированный алгоритм факторизации Ленстры Сложность ${\displaystyle O(n^{1/3}\log ^{2}n)}$. [1] Следует отметить, что несмотря на относительно неплохую эффективность среди экспоненциальных алгоритмов, в алгоритме Ленстры есть необходимость неоднократно вычислять квадратный корень в одном из шагов алгоритма, что, безусловно, является более трудоёмким, чем сложение или вычитание[2]. Пусть ${\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 i\geq 2}$: ${\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}$. Примечания H. W. Lenstra. Divisors in Residue Classes // Mathematics of Computation. — 1984. — Т. 42, № 165. Архивировано 5 мая 2019 года. Василенко, 2003, с. 73. Василенко, 2003, с. 69. Литература Василенко О. Н. Теоретико-числовые алгоритмы в криптографии — М.: МЦНМО, 2003. — 328 с. — ISBN 978-5-94057-103-2