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

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

Алгоритм Ленстры — Ленстры — Ловаса (ЛЛЛ-алгоритм, 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]}$), если он удовлетворяет следующим свойствам:

1. Для всех $i,j$ таких, что $1\leqslant j<i\leqslant d\colon \left|\mu _{i,j}\right|\leqslant 0{,}5$. (условие уменьшения размера)
2. Для $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}})$ — норма кратчайшего вектора решётки, тогда:

1. Первый вектор базиса не может быть значительно длиннее кратчайшего ненулевого вектора:
   ${\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}})$.
2. Первый вектор базиса ограничен определителем решётки:
   ${\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}$.
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}})}$. В частности, $\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}}}$ (выбор параметра зависит от конкретной задачи).

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

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

В алгоритме $\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. Процесс ортогонализации Грама-Шмидта
   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}}}$
2. При $k=2$ имеем $\mu _{2,1}<{\frac {1}{2}}$ и $(\delta -\mu _{2,1}^{2})\|\mathbf {b} _{1}^{*}\|^{2}\leqslant \|\mathbf {b} _{2}^{*}\|^{2}$, поэтому переходим к следующему шагу.
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}$ меняются местами.
4. Теперь возвращаемся к шагу 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) алгоритм используется для поиска кратчайшего вектора решётки, так как алгоритм в результате находит целый набор кратчайших векторов.

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

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

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

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

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

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

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

Литература

• 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.