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

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

Алгоритм был разработан голландскими математиками Арьеном Ленстрой и Хендриком Ленстрой совместно с венгерским математиком Ласло Ловасом в 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.