Interested Article - Алгоритм Ленстры — Ленстры — Ловаса

Редукция базиса решетки в двумерном пространстве: решётка представлена синими точками, исходный базис — черные векторы, редуцированный базис — красные векторы.

Алгоритм Ленстры — Ленстры — Ловаса ( ЛЛЛ-алгоритм , LLL-алгоритм ) — алгоритм , разработанный Арьеном Ленстрой , Хендриком Ленстрой и Ласло Ловасом в 1982 году . За полиномиальное время алгоритм преобразует базис на решётке (подгруппе $\mathbb {R} ^{n}$ ) в кратчайший почти ортогональный базис на этой же решётке. По состоянию на 2019 год алгоритм Ленстры — Ленстры — Ловаса является одним из самых эффективных для вычисления редуцированного базиса в решётках больших размерностей . Он актуален прежде всего в задачах, сводящихся к поиску кратчайшего вектора решётки.

История

Алгоритм был разработан голландскими математиками Арьеном Ленстрой и Хендриком Ленстрой совместно с венгерским математиком Ласло Ловасом в 1982 году .

Основной предпосылкой для создания ЛЛЛ-алгоритма послужило то, что процесс Грама ― Шмидта работает только с векторами, компоненты которых являются вещественными числами . Для векторного пространства $\mathbb {R} ^{n}$ процесс Грама ― Шмидта позволяет преобразовать произвольный базис в ортонормированный («идеал», к которому стремится ЛЛЛ-алгоритм). Но процесс Грама ― Шмидта не гарантирует того, что на выходе каждый из векторов будет целочисленной линейной комбинацией исходного базиса. Таким образом, полученный в результате набор векторов может и не являться базисом исходной решётки. Это привело к необходимости создания специального алгоритма для работы с решётками .

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

Редукция базиса

Решётка в евклидовом пространстве — это подгруппа группы $(\mathbb {R} ^{n},+)$ , порожденная $d$ линейно независимыми векторами из $\mathbb {R} ^{n}$ , называемыми базисом решётки. Любой вектор решётки может быть представлен целочисленной линейной комбинацией базисных векторов . Базис решётки определяется неоднозначно: на рисунке изображены два различных базиса одной и той же решётки.

Редукция базиса заключается в приведении к особому виду, удовлетворяющему некоторым свойствам. Редуцированный базис должен быть, по возможности, наиболее коротким среди всех базисов решётки и близким к ортогональному (что выражается в том, что итоговые коэффициенты Грама — Шмидта должны быть не больше $1/2$ ) .

Пусть в результате преобразования базиса $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ с помощью процесса Грама ― Шмидта получен базис $\mathbf {B} ^{*}=\{\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\dots ,\mathbf {b} _{d}^{*}\}$ , с коэффициентами Грама — Шмидта, определяемыми следующим образом:

{\textstyle \mu _{i,j}={\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}}

, для всех

j,i

таких, что

1\leqslant j<i\leqslant d

.

Тогда (упорядоченный) базис $\mathbf {B}$ называется $\delta$ -ЛЛЛ-редуцированным базисом (где параметр $\delta$ находится в промежутке ${\textstyle (0.25,1]}$ ), если он удовлетворяет следующим свойствам :

Для всех $i,j$ таких, что $1\leqslant j<i\leqslant d\colon \left|\mu _{i,j}\right|\leqslant 0{,}5$ . (условие уменьшения размера)
Для $k=1,2,\dots ,d$ имеет место: $(\delta -\mu _{k,k-1}^{2})\|\mathbf {b} _{k-1}^{*}\|^{2}\leqslant \|\mathbf {b} _{k}^{*}\|^{2}$ . (условие Ловаса)

Здесь $\|\mathbf {b} \|$ — норма вектора , $\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle$ — cкалярное произведение векторов.

Изначально Ленстра, Ленстра и Ловас в своей статье продемонстрировали работу алгоритма для параметра ${\textstyle \delta ={\frac {3}{4}}}$ . Несмотря на то что алгоритм остаётся корректным и для $\delta =1$ , его работа за полиномиальное время гарантируется только для $\delta$ в промежутке $(0.25,1)$ .

Свойства редуцированного базиса

Пусть $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ — сокращённый алгоритмом ЛЛЛ с параметром $\delta$ базис на решётке ${\mathcal {L}}$ . Из определения такого базиса можно получить несколько свойств $\mathbf {B}$ . Пусть $\lambda _{1}({\mathcal {L}})$ — норма кратчайшего вектора решётки, тогда:

Первый вектор базиса не может быть значительно длиннее кратчайшего ненулевого вектора :

${\textstyle \|\mathbf {b} _{1}\|\leqslant \left({\frac {2}{\sqrt {4\delta -1}}}\right)^{d-1}\cdot \lambda _{1}({\mathcal {L}})}$ . В частности, для $\delta =3/4$ получается $\|\mathbf {b} _{1}\|\leqslant 2^{(d-1)/2}\cdot \lambda _{1}({\mathcal {L}})$ .
Первый вектор базиса ограничен определителем решётки :

${\textstyle \|\mathbf {b} _{1}\|\leqslant \left({\frac {2}{\sqrt {4\delta -1}}}\right)^{(d-1)/2}\cdot \det({\mathcal {L}})^{1/d}}$ . В частности, для $\delta =3/4$ получается $\|\mathbf {b} _{1}\|\leqslant 2^{(d-1)/4}\cdot (\det {\mathcal {L}})^{1/d}$ .
Произведение норм векторов не может быть сильно больше определителя решётки:

${\textstyle \prod _{i=1}^{d}\|\mathbf {b} _{i}\|\leqslant \left({\frac {2}{\sqrt {4\delta -1}}}\right)^{d(d-1)/2}\cdot \det({\mathcal {L}})}$ . В частности, $\prod _{i=1}^{d}\|\mathbf {b} _{i}\|\leqslant 2^{d(d-1)/4}\cdot \det({\mathcal {L}})$ для $\delta =3/4$ .

Базис, преобразованный методом ЛЛЛ, почти самый короткий из всех возможных, в том смысле, что существуют абсолютные границы $c_{i}>1$ такие, что первый базисный вектор не более чем в $c_{1}$ раз длиннее самого короткого вектора решётки, аналогично, второй вектор базиса не более чем в $c_{2}$ раз превосходит второй кратчайший вектор решётки и так далее (что прямо следует из свойства 1) .

Алгоритм

Входные данные :

базис решётки

\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\in \displaystyle \mathbb {R} ^{3}

(состоит из линейно независимых векторов),

параметр

\delta

c

{\textstyle {\frac {1}{4}}<\delta <1}

, чаще всего

{\textstyle \delta ={\frac {3}{4}}}

(выбор параметра зависит от конкретной задачи).

Последовательность действий :

Сначала создается копия исходного базиса, которая ортогонализуется для того, чтобы по ходу алгоритма текущий базис сравнивался с полученной копией на предмет ортогональности ( $\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\dots ,\mathbf {b} _{d}^{*}$ ).
Если какой-либо коэффициент Грама — Шмидта $\vert \mu _{k,j}\vert$ (с $j<k$ ) по модулю больше $0{,}5$ , то проекция одного из векторов $\mathbf {b} _{k}$ текущего базиса на вектор $\mathbf {b} _{j}^{*}$ ортогонализованного базиса с другим номером составляет больше половины $\mathbf {b} _{j}^{*}$ . Это говорит о том, что необходимо вычесть из вектора $\mathbf {b} _{k}$ вектор $\mathbf {b} _{j}$ , домноженный на округленный $\vert \mu _{k,j}\vert$ (округление нужно, так как вектор решётки остается вектором этой же решётки только при умножении на целое число, что следует из её определения). Тогда $\vert \mu _{k,j}\vert$ станет меньше $0{,}5$ , так как теперь проекция $\mathbf {b} _{k}$ на $\mathbf {b} _{j}^{*}$ будет меньше половины $\mathbf {b} _{j}^{*}$ . Таким образом производится проверка соответствию 1-му условию из определения ЛЛЛ-редуцированного базиса.
Пересчитывается $\mu _{k,j}$ для $j<k$ .
Для $\mathbf {b} _{k}$ проверяется 2-е условие, введенное авторами алгоритма как определение ЛЛЛ-редуцированного базиса . Если условие не выполнено, то индексы проверяемых векторов меняются местами. И условие проверяется снова для того же вектора (уже с новым индексом).
Пересчитываются $\mathbf {b} _{k}^{*},\mathbf {b} _{k-1}^{*},\langle \mathbf {b} _{k}^{*},\mathbf {b} _{k}^{*}\rangle ,\langle \mathbf {b} _{k-1}^{*},\mathbf {b} _{k-1}^{*}\rangle$ для $k>1$ и $\mu _{k-1,j},\mu _{k,j}$ для $j<k$
Если остался какой-либо $\mu _{k,j}$ , по модулю превышающий $0{,}5$ (уже с другим $k$ ), то надо вернуться к пункту 2.
Когда все условия проверены и сделаны изменения, алгоритм завершает работу.

В алгоритме $\lfloor \mu _{k,j}\rceil$ — округление по правилам математики. Процесс алгоритма, описанный на псевдокоде :

  ortho  $:=\mathrm {gramSchmidt} (\{\mathbf {b} _{1},\dots ,\mathbf {b} _{d}\})=\{\mathbf {b} _{1}^{*},\dots ,\mathbf {b} _{d}^{*}\}$  
  (выполнить процесс Грама — Шмидта без нормировки);
  определить  ${\textstyle \mu _{k,j}:={\frac {\langle \mathbf {b} _{k},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}}$ , всегда подразумевая наиболее актуальные значения  $\mathbf {b} _{k},\mathbf {b} _{j}^{*}$ 
  присвоить  $k=2$ 
  пока  $k\leqslant d$ :
    для j от  $k-1$  до 0:
       если  ${\textstyle |\mu _{k,j}|>{\frac {1}{2}}}$ , то:
           $\mathbf {b} _{k}=\mathbf {b} _{k}-\lfloor \mu _{k,j}\rceil \mathbf {b} _{j}$ ;
          Обновить значения  $|\mu _{k,j}|$  для  $j<k$ ;
       конец условия;
    конец цикла;
    если  ${\textstyle (\delta -\mu _{k,k-1}^{2})\|\mathbf {b} _{k-1}^{*}\|^{2}\leqslant \|\mathbf {b} _{k}^{*}\|^{2}}$ , то:
        $k=k+1$ 
    иначе:
       поменять  $\mathbf {b} _{k}$  и  $\mathbf {b} _{k-1}$  местами;
       Обновить значения  $\mathbf {b} _{k}^{*},\mathbf {b} _{k-1}^{*},\langle \mathbf {b} _{k}^{*},\mathbf {b} _{k}^{*}\rangle ,\langle \mathbf {b} _{k-1}^{*},\mathbf {b} _{k-1}^{*}\rangle$  для  $k>1$ ;  $\mu _{k-1,j},\mu _{k,j}$  для  $j<k$ ;
        $k=\max(k-1,1)$ ;
    конец условия;
  конец цикла.

Выходные данные: редуцированный базис: $\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}$ .

Вычислительная сложность

На входе имеется базис $n$ -мерных векторов $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ с $\ d\leqslant n$ .

Если вектора базиса состоят из целочисленных компонент, алгоритм приближает кратчайший почти ортогональный базис за полиномиальное время $O(d^{5}n\log ^{3}B)$ , где $B$ — максимальная длина $\mathbf {b} _{i}$ по евклидовой норме , то есть $B=\max \left(\|\mathbf {b} _{1}\|_{2},\|\mathbf {b} _{2}\|_{2},...,\|\mathbf {b} _{d}\|_{2}\right)$ . Основной цикл алгоритма ЛЛЛ требует $O(d^{2}\log B)$ итераций и работает с числами длины $O(d\log B)$ . Так как на каждой итерации происходит обработка $d$ векторов длины $n$ , в итоге алгоритм требует $O(d^{3}n\log ^{3}B)$ арифметических операций. Применение наивных алгоритмов сложения и умножения целых чисел даёт в итоге $O(d^{5}n\log ^{3}B)$ битовых операций .

В случае, когда у решётки задан базис с рациональными компонентами, эти рациональные числа сначала необходимо преобразовать в целые путем умножения базисных векторов на знаменатели их компонент (множество знаменателей ограничено некоторым целым числом $X$ ). Но тогда операции будут производиться уже над целыми числами, не превышающими $X^{nd}$ . В итоге будет максимум $O(d^{8}n^{4}\log ^{3}X)$ битовых операций . Для случая, когда решётка задана в $\mathbb {R} ^{n}$ , сложность алгоритма остается такой же, но увеличивается количество битовых операций. Так как в компьютерном представлении любое вещественное число заменяется рациональным в силу ограниченности битового представления, полученная оценка верна и для вещественных решёток .

В то же время для размерностей меньше чем 4 задача редукции базиса более эффективно решается .

Пример

Пример, приводимый Вибом Босмой .

Пусть базис решётки $\mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3}\in \displaystyle \mathbb {Z} ^{3}$ (как подгруппа $(\mathbb {R} ^{n},+)$ ), задан столбцами матрицы:

{\begin{bmatrix}1&-1&3\\1&0&5\\1&2&6\end{bmatrix}}

По ходу алгоритма получается следующее:

Процесс ортогонализации Грама-Шмидта
1. ${\textstyle b_{1}^{*}=b_{1}={\begin{bmatrix}1\\1\\1\end{bmatrix}},B_{1}=\langle b_{1}^{*},b_{1}^{*}\rangle =3}$
2. ${\textstyle \mu _{2,1}={\frac {\langle b_{2},b_{1}^{*}\rangle }{B_{1}}}={\frac {1}{3}}\left(<{\frac {1}{2}}\right)}$ , $b_{2}^{*}=b_{2}-\mu _{2,1}b_{1}^{*}={\begin{bmatrix}{\frac {-4}{3}}\\{\frac {-1}{3}}\\{\frac {5}{3}}\end{bmatrix}}$ и ${\textstyle B_{2}=\langle b_{2}^{*},b_{2}^{*}\rangle ={\frac {14}{3}}.}$
3. ${\textstyle \mu _{3,1}={\frac {14}{3}}(>{\frac {1}{2}})}$ , поэтому $b_{3}^{*}={\begin{bmatrix}{\frac {-5}{3}}\\{\frac {1}{3}}\\{\frac {4}{3}}\end{bmatrix}}$ и ${\textstyle \mu _{3,2}={\frac {\langle b_{3},b_{2}^{*}\rangle }{B_{2}}}={\frac {13}{14}}\left(>{\frac {1}{2}}\right)}$ , тогда ${\textstyle b_{3}^{*}={\begin{bmatrix}{\frac {-6}{14}}\\{\frac {9}{14}}\\{\frac {-3}{14}}\end{bmatrix}}}$ и ${\textstyle B_{3}={\frac {9}{14}}}$
При $k=2$ имеем $\mu _{2,1}<{\frac {1}{2}}$ и $(\delta -\mu _{2,1}^{2})\|\mathbf {b} _{1}^{*}\|^{2}\leqslant \|\mathbf {b} _{2}^{*}\|^{2}$ , поэтому переходим к следующему шагу.
При $k=3$ $k=3$ имеем:
1. $\lfloor \mu _{3,2}\rceil =1$ , значит ${\textstyle b_{3}=b_{3}-1\cdot b_{2}={\begin{bmatrix}3\\5\\6\end{bmatrix}}-{\begin{bmatrix}-1\\0\\2\end{bmatrix}}={\begin{bmatrix}4\\5\\4\end{bmatrix}}}$ , теперь ${\textstyle \mu _{3,2}={\frac {13}{14}}-1=-{\frac {1}{14}},\mu _{3,1}={\frac {13}{3}}}$
2. $\lfloor \mu _{3,1}\rceil =4$ , значит ${\textstyle b_{3}=b_{3}-4\cdot b_{1}={\begin{bmatrix}4\\5\\4\end{bmatrix}}-{\begin{bmatrix}4\\4\\4\end{bmatrix}}={\begin{bmatrix}0\\1\\0\end{bmatrix}}}$ , теперь ${\textstyle \mu _{3,2}=-{\frac {1}{14}},\mu _{3,1}={\frac {1}{3}}}$
3. $(\delta -\mu _{3,2}^{2})\|\mathbf {b} _{2}^{*}\|^{2}>\|\mathbf {b} _{3}^{*}\|^{2}$ , поэтому $b_{3}$ и $b_{2}$ меняются местами.
Теперь возвращаемся к шагу 1, при этом промежуточная матрица $(\mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3})$ имеет вид ${\begin{bmatrix}1&0&-1\\1&1&0\\1&0&2\end{bmatrix}}$

Выходные данные: базис, редуцированный методом Ленстры — Ленстры — Ловаса:

{\begin{bmatrix}0&1&-1\\1&0&0\\0&1&2\end{bmatrix}}

Применение

Алгоритм часто применяется в рамках метода MIMO (пространственное кодирования сигнала) для декодирования сигналов, полученных несколькими антеннами , и в криптосистемах с открытым ключом : , RSA с конкретными настройками, NTRUEncrypt и так далее. Алгоритм может быть использован для нахождения целых решений в разных задачах теории чисел, в частности для поиска корней многочлена в целых числах .

В процессе атак на криптосистемы с открытым ключом ( NTRU ) алгоритм используется для поиска кратчайшего вектора решётки, так как алгоритм в результате находит целый набор кратчайших векторов .

В криптоанализе задача, так же как в случае с NTRU, сводится к поиску кратчайшего вектора базиса решётки, который находится за полиномиальное (от размерности базиса) время .

В задачах о ранце, в частности, для атаки на криптосистемe Меркла — Хеллмана алгоритм ЛЛЛ ищет редуцированный базис решётки .

Вариации и обобщения

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

Реализации алгоритма

Программно алгоритм реализован в следующем программном обеспечении:

В как автономная реализация ;
В GAP как функция LLLReducedBasis ;
В как функция LLL в библиотеке LLLBases ;
В как функции LLL и LLLGram ;
В Maple как функция IntegerRelations[LLL] ;
В Mathematica как функция LatticeReduce ;
В как модуль LLL ;
В как функция qflll ;
В как функция analysis.get_lll_reduced_lattice ;
В SageMath как метод LLL , реализованный в fpLLL и NTL .

Примечания

↑ A. K. Lenstra, H. W. Lenstra Jr., L. Lovász. Factoring polynomials with rational coefficients // Mathematische Annalen . — 1982. — С. 515—534 . — ISSN . — doi : .
↑ , 1 The History of the LLL-Algorithm.
↑ Galbraith, Steven. 17. Lattice Reduction // (англ.) . — 2012. 20 сентября 2015 года.
↑ Xinyue, Deng. (англ.) // Massachusetts Institute of Technology. — P. 9—10 . 8 декабря 2019 года.
Чередник И. В. // 3-е изд. — Дискрет. матем., 2014. — Т. 26 . — С. 127—135 .
↑ Regev, Oded. // New York University. 20 марта 2021 года.
↑ Hoffstein, Jeffrey; Pipher, Jill; Silverman, J.H. An Introduction to Mathematical Cryptography (англ.) . — (англ.) ( , 2008. — P. 411. — ISBN 978-0-387-77993-5 .
Nguyen, Phong Q., Stehlé, Damien. (англ.) // ACM Transactions on Algorithms. — P. 1–48 . — doi : .
Bosma, Wieb. // Computer Algebra. — 2007. 8 мая 2019 года.
Shahriar Shahabuddin, Janne Janhunen, Zaheer Khan, Markku Juntti, Amanullah Ghazi. A customized lattice reduction multiprocessor for MIMO detection // 2015 IEEE International Symposium on Circuits and Systems (ISCAS). — 2015. — arXiv : . — doi : .
D. Simon. // LLL+25 Conference. — Caen, France. 6 мая 2021 года.
Abderrahmane, Nitaj. // International Association for Cryptologic Research. — Caen, France. 21 декабря 2019 года.
Bleichenbacher, Daniel and May, Alexander. // International Association for Cryptologic Research. — Darmstadt, Germany. 24 июня 2021 года.
Liu, Jiayang, Bi, Jingguo and Xu, Songyan. // IEEE. — Beijing 100084, China. 17 июня 2021 года.
, 4 Progress on LLL and Lattice Reduction.
The FPLLL development team. . — 2016. 17 февраля 2020 года.
. GAP . Дата обращения: 10 декабря 2019. 19 декабря 2019 года.
. Macaulay2 . Дата обращения: 10 декабря 2019. 10 декабря 2019 года.
. Magma . Дата обращения: 10 декабря 2019. 10 декабря 2019 года.
. Maple . Дата обращения: 10 декабря 2019. 18 сентября 2020 года.
. Wolfram Language Documentation . Дата обращения: 10 декабря 2019. 10 декабря 2019 года.
. NTL . Дата обращения: 10 декабря 2019. 17 августа 2018 года.
. PARI/GP . Дата обращения: 10 декабря 2019. 18 декабря 2019 года.
. pymatgen . Дата обращения: 27 декабря 2019. 18 декабря 2019 года.
. sage . Дата обращения: 18 декабря 2019. 6 мая 2021 года.

Литература

Huguette, Napias. // J. The. Nombr. Bordeaux. — 1996. — doi : .
Cohen, Henri. A course in computational algebraic number theory (англ.) . — (англ.) ( , 2000. — Vol. 138. — (GTM). — ISBN 3-540-55640-0 .
Borwein, Peter. (англ.) . — 2002. — ISBN 0-387-95444-9 .
Hoffstein, Jeffrey; Pipher, Jill; Silverman, J.H. An Introduction to Mathematical Cryptography (англ.) . — (англ.) ( , 2008. — ISBN 978-0-387-77993-5 .
Luk, Franklin T.; Qiao, Sanzheng. A pivoted LLL algorithm // Lin. Alg. Appl.. — 2011. — Т. 434 , № 11 . — С. 2296—2307 . — doi : .
The LLL Algorithm : Survey and Applications / Ed. by Phong Q. Nguyen and Brigitte Vallée. — Springer, 2010. — ISBN 978-3-642-02295-1 . — doi : .
Murray R. Bremner. Lattice Basis Reduction : An Introduction to the LLL Algorithm and Its Applications. — CRC Press, 2011. — ISBN 9781439807026 .

[:1-1] A. K. Lenstra, H. W. Lenstra Jr., L. Lovász. Factoring polynomials with rational coefficients // Mathematische Annalen . — 1982. — С. 515—534 . — ISSN . — doi : .

[history-2] , 1 The History of the LLL-Algorithm.

[:0-3] Galbraith, Steven. 17. Lattice Reduction // (англ.) . — 2012. 20 сентября 2015 года.

[Introduction_to_LLL-4] Xinyue, Deng. (англ.) // Massachusetts Institute of Technology. — P. 9—10 . 8 декабря 2019 года.

[5] Чередник И. В. // 3-е изд. — Дискрет. матем., 2014. — Т. 26 . — С. 127—135 .

[regev_lll-6] Regev, Oded. // New York University. 20 марта 2021 года.

[2:-7] Hoffstein, Jeffrey; Pipher, Jill; Silverman, J.H. An Introduction to Mathematical Cryptography (англ.) . — (англ.) ( , 2008. — P. 411. — ISBN 978-0-387-77993-5 .

[8] Nguyen, Phong Q., Stehlé, Damien. (англ.) // ACM Transactions on Algorithms. — P. 1–48 . — doi : .

[9] Bosma, Wieb. // Computer Algebra. — 2007. 8 мая 2019 года.

[10] Shahriar Shahabuddin, Janne Janhunen, Zaheer Khan, Markku Juntti, Amanullah Ghazi. A customized lattice reduction multiprocessor for MIMO detection // 2015 IEEE International Symposium on Circuits and Systems (ISCAS). — 2015. — arXiv : . — doi : .

[11] D. Simon. // LLL+25 Conference. — Caen, France. 6 мая 2021 года.

[12] Abderrahmane, Nitaj. // International Association for Cryptologic Research. — Caen, France. 21 декабря 2019 года.

[13] Bleichenbacher, Daniel and May, Alexander. // International Association for Cryptologic Research. — Darmstadt, Germany. 24 июня 2021 года.

[14] Liu, Jiayang, Bi, Jingguo and Xu, Songyan. // IEEE. — Beijing 100084, China. 17 июня 2021 года.

[progress-15] , 4 Progress on LLL and Lattice Reduction.

[16] The FPLLL development team. . — 2016. 17 февраля 2020 года.

[17] . GAP . Дата обращения: 10 декабря 2019. 19 декабря 2019 года.

[18] . Macaulay2 . Дата обращения: 10 декабря 2019. 10 декабря 2019 года.

[19] . Magma . Дата обращения: 10 декабря 2019. 10 декабря 2019 года.

[20] . Maple . Дата обращения: 10 декабря 2019. 18 сентября 2020 года.

[21] . Wolfram Language Documentation . Дата обращения: 10 декабря 2019. 10 декабря 2019 года.

[22] . NTL . Дата обращения: 10 декабря 2019. 17 августа 2018 года.

[23] . PARI/GP . Дата обращения: 10 декабря 2019. 18 декабря 2019 года.

[24] . pymatgen . Дата обращения: 27 декабря 2019. 18 декабря 2019 года.

[25] . sage . Дата обращения: 18 декабря 2019. 6 мая 2021 года.

Теоретико-числовые алгоритмы
Тесты простоты	Миллера Миллера — Рабина Люка — Лемера Пепина Агравала — Каяла — Саксены Соловея — Штрассена
Поиск простых чисел	Перебор делителей Решето Эратосфена Решето Аткина Решето Сундарама
Факторизация	Перебор делителей Метод Ферма p −1-метод Полларда ρ-алгоритм Полларда Метод Лемана Метод эллиптических кривых (алгоритм Ленстры) Алгоритм Диксона Квадратичное решето
Дискретное логарифмирование	Алгоритм Гельфонда — Шенкса Алгоритм Полига — Хеллмана ρ-метод Полларда Алгоритм «кенгуру» Полларда Алгоритм Адлемана Алгоритм COS
Нахождение НОД	Алгоритм Евклида Расширенный алгоритм Бинарный алгоритм
Арифметика по модулю	Алгоритм Монтгомери Китайская теорема об остатках
Умножение и деление чисел	Алгоритм Карацубы Алгоритм Тоома — Кука Алгоритм Шёнхаге — Штрассена Алгоритм Фюрера Алгоритм Харви — ван дер Хувена Алгоритм Бурникеля — Циглера
Вычисление квадратного корня	Алгоритм Тонелли — Шенкса Алгоритм Берлекэмпа — Рабина

Interested Article - Алгоритм Ленстры — Ленстры — Ловаса

Содержание

История

Редукция базиса

Свойства редуцированного базиса

Алгоритм

Вычислительная сложность

Пример

Применение

Вариации и обобщения

Реализации алгоритма

Примечания

Литература

Same as Алгоритм Ленстры — Ленстры — Ловаса

Алгоритмическая локальная лемма Ловаса

Алгоритм Шора

A5 (алгоритм шифрования)

Алгоритм Гаусса вычисления даты Пасхи

Алгоритм Витерби

Алгоритм прямого-обратного хода

Алгоритм Баума — Велша

Алгоритм Тодда — Коксетера

Алгоритм Гэйла — Шепли

Алгоритм Чена

Camellia (алгоритм)

Алгоритм сортировки

EM-алгоритм

Алгоритм Кока — Янгера — Касами

Алгоритм Прима

Алгоритм Евклида

Параллельный алгоритм

Алгоритм Гилберта — Джонсона — Кирти

Алгоритм двойников

Нормальный алгоритм

Алгоритм Ярроу

Алгоритм Fortuna

Алгоритм планирования по ближайшему сроку завершения

Алгоритм Лианга — Барски

The title for the last searches