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

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

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

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

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

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

Пусть в результате преобразования базиса ${\displaystyle \mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}}$ с помощью процесса Грама ― Шмидта получен базис ${\displaystyle \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 }}}$ , для всех ${\displaystyle j,i}$ таких, что ${\displaystyle 1\leqslant j<i\leqslant d}$ .

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

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

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

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

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

1. Первый вектор базиса не может быть значительно длиннее кратчайшего ненулевого вектора:
   ${\textstyle \|\mathbf {b} _{1}\|\leqslant \left({\frac {2}{\sqrt {4\delta -1}}}\right)^{d-1}\cdot \lambda _{1}({\mathcal {L}})}$ . В частности, для ${\displaystyle \delta =3/4}$ получается ${\displaystyle \|\mathbf {b} _{1}\|\leqslant 2^{(d-1)/2}\cdot \lambda _{1}({\mathcal {L}})}$ ^[6].
2. Первый вектор базиса ограничен определителем решётки:
   ${\textstyle \|\mathbf {b} _{1}\|\leqslant \left({\frac {2}{\sqrt {4\delta -1}}}\right)^{(d-1)/2}\cdot \det({\mathcal {L}})^{1/d}}$ . В частности, для ${\displaystyle \delta =3/4}$ получается ${\displaystyle \|\mathbf {b} _{1}\|\leqslant 2^{(d-1)/4}\cdot (\det {\mathcal {L}})^{1/d}}$ ^[3].
3. Произведение норм векторов не может быть сильно больше определителя решётки:
   ${\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}})}$ . В частности, ${\displaystyle \prod _{i=1}^{d}\|\mathbf {b} _{i}\|\leqslant 2^{d(d-1)/4}\cdot \det({\mathcal {L}})}$ для ${\displaystyle \delta =3/4}$ ^[3].

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

Входные данные^[7]:

базис решётки ${\displaystyle \mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\in \displaystyle \mathbb {R} ^{3}}$ (состоит из линейно независимых векторов),

параметр ${\displaystyle \delta }$ c ${\textstyle {\frac {1}{4}}<\delta <1}$ , чаще всего ${\textstyle \delta ={\frac {3}{4}}}$ (выбор параметра зависит от конкретной задачи).

Последовательность действий^[4]:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В криптоанализе RSA c малой CRT-экспонентой^[англ.] задача, так же как в случае с NTRU, сводится к поиску кратчайшего вектора базиса решётки, который находится за полиномиальное (от размерности базиса) время^[13].

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

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

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

• В fpLLL как автономная реализация^[16];
• В GAP как функция LLLReducedBasis ^[17];
• В Macaulay2^[англ.] как функция LLL в библиотеке LLLBases ^[18];
• В Magma^[англ.] как функции LLL и LLLGram ^[19];
• В Maple как функция IntegerRelations[LLL] ^[20];
• В Mathematica как функция LatticeReduce ^[21];
• В Number Theory Library (NTL) как модуль LLL ^[22];
• В PARI/GP^[англ.] как функция qflll ^[23];
• В Pymatgen как функция analysis.get_lll_reduced_lattice ^[24];
• В SageMath как метод LLL, реализованный в fpLLL и NTL^[25].

• Huguette, Napias. A generalization of the LLL algorithm over euclidean rings or orders // J. The. Nombr. Bordeaux. — 1996. — doi:10.5802/jtnb.176.
• Cohen, Henri. A course in computational algebraic number theory (англ.). — Springer^[англ.], 2000. — Vol. 138. — (GTM). — ISBN 3-540-55640-0.
• Borwein, Peter. Computational Excursions in Analysis and Number Theory (англ.). — 2002. — ISBN 0-387-95444-9.
• Hoffstein, Jeffrey; Pipher, Jill; Silverman, J.H. An Introduction to Mathematical Cryptography (англ.). — Springer^[англ.], 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:10.1016/j.laa.2010.04.003.
• The LLL Algorithm : Survey and Applications / Ed. by Phong Q. Nguyen and Brigitte Vallée. — Springer, 2010. — ISBN 978-3-642-02295-1. — doi:10.1007/978-3-642-02295-1.
• Murray R. Bremner. Lattice Basis Reduction : An Introduction to the LLL Algorithm and Its Applications. — CRC Press, 2011. — ISBN 9781439807026.