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

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

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

История

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

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

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

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

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

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

Пусть в результате преобразования базиса $𝐁=\{{𝐛}_1,{𝐛}_2,\dots ,{𝐛}_d\}$ с помощью процесса Грама ― Шмидта получен базис ${𝐁}^{*}=\{{𝐛}_1^{*},{𝐛}_2^{*},\dots ,{𝐛}_d^{*}\}$, с коэффициентами Грама — Шмидта, определяемыми следующим образом:

${\mu }_{i,j}=\frac{⟨{𝐛}_i,{𝐛}_j^{*}⟩}{⟨{𝐛}_j^{*},{𝐛}_j^{*}⟩}$, для всех $j,i$ таких, что $1⩽j<i⩽d$.

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

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

Здесь $\Vert 𝐛\Vert$ — норма вектора, $⟨{𝐛}_i,{𝐛}_j^{*}⟩$ — cкалярное произведение векторов.

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

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

Пусть $𝐁=\{{𝐛}_1,{𝐛}_2,\dots ,{𝐛}_d\}$ — сокращённый алгоритмом ЛЛЛ с параметром $\delta$ базис на решётке $ℒ$. Из определения такого базиса можно получить несколько свойств $𝐁$. Пусть ${\lambda }_1(ℒ)$ — норма кратчайшего вектора решётки, тогда:

1. Первый вектор базиса не может быть значительно длиннее кратчайшего ненулевого вектора:Шаблон:Pb$\Vert {𝐛}_1\Vert ⩽{\left(\frac{2}{\sqrt{4\delta -1}}\right)}^{d-1}\cdot {\lambda }_1(ℒ)$. В частности, для $\delta =3/4$ получается $\Vert {𝐛}_1\Vert ⩽2^{(d-1)/2}\cdot {\lambda }_1(ℒ)$.
2. Первый вектор базиса ограничен определителем решётки:Шаблон:Pb$\Vert {𝐛}_1\Vert ⩽{\left(\frac{2}{\sqrt{4\delta -1}}\right)}^{(d-1)/2}\cdot \det (ℒ{)}^{1/d}$. В частности, для $\delta =3/4$ получается $\Vert {𝐛}_1\Vert ⩽2^{(d-1)/4}\cdot (\det ℒ{)}^{1/d}$.
3. Произведение норм векторов не может быть сильно больше определителя решётки:Шаблон:Pb${\prod }_{i=1}^d\Vert {𝐛}_i\Vert ⩽{\left(\frac{2}{\sqrt{4\delta -1}}\right)}^{d(d-1)/2}\cdot \det (ℒ)$. В частности, $\prod _{i=1}^d\Vert {𝐛}_i\Vert ⩽2^{d(d-1)/4}\cdot \det (ℒ)$ для $\delta =3/4$.

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

Алгоритм

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

базис решётки ${𝐛}_1,{𝐛}_2,\dots ,{𝐛}_d\in {ℝ}^3$ (состоит из линейно независимых векторов),

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

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

  Шаблон:Nowrap 
  (выполнить процесс Грама — Шмидта без нормировки);
  Шаблон:Nowrap всегда подразумевая Шаблон:Nowrap
  Шаблон:Nowrap
  Шаблон:Nowrap
    для Шаблон:Mvar Шаблон:Nowrap
       если $|{\mu }_{k,j}|>\frac{1}{2}$, то:
          Шаблон:Nowrap
          Обновить значения $|{\mu }_{k,j}|$ для $j<k$;
       конец условия;
    конец цикла;
    Шаблон:Nowrap
       Шаблон:Nowrap
    иначе:
       Шаблон:Nowrap
       Обновить значения ${𝐛}_k^{*},{𝐛}_{k-1}^{*},⟨{𝐛}_k^{*},{𝐛}_k^{*}⟩,⟨{𝐛}_{k-1}^{*},{𝐛}_{k-1}^{*}⟩$ для $k>1$; ${\mu }_{k-1,j},{\mu }_{k,j}$ для $j<k$;
       $k=\max (k-1,1)$;
    конец условия;
  конец цикла.

Выходные данные: редуцированный базис: ${𝐛}_1,{𝐛}_2,\dots ,{𝐛}_d$.

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

На входе имеется базис $n$-мерных векторов $𝐁=\{{𝐛}_1,{𝐛}_2,\dots ,{𝐛}_d\}$ с $d⩽n$.

Если вектора базиса состоят из целочисленных компонент, алгоритм приближает кратчайший почти ортогональный базис за полиномиальное время $O(d^{5}n{\log }^{3}B)$, где $B$ — максимальная длина ${𝐛}_i$ по евклидовой норме, то есть $B=\max (\Vert {𝐛}_1{\Vert }_2,\Vert {𝐛}_2{\Vert }_2,...,\Vert {𝐛}_d{\Vert }_2)$. Основной цикл алгоритма ЛЛЛ требует $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)$ битовых операций. Для случая, когда решётка задана в ${ℝ}^n$, сложность алгоритма остается такой же, но увеличивается количество битовых операций. Так как в компьютерном представлении любое вещественное число заменяется рациональным в силу ограниченности битового представления, полученная оценка верна и для вещественных решёток.

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

Пример

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

Пусть базис решётки ${𝐛}_1,{𝐛}_2,{𝐛}_3\in {\mathbb{Z}}^3$ (как подгруппа $({ℝ}^n,+)$), задан столбцами матрицы:

$\left[\begin{array}{ccc}1& -1& 3\\ 1& 0& 5\\ 1& 2& 6\end{array}\right]$

По ходу алгоритма получается следующее: Шаблон:Ordered list Выходные данные: базис, редуцированный методом Ленстры — Ленстры — Ловаса:

$\left[\begin{array}{ccc}0& 1& -1\\ 1& 0& 0\\ 0& 1& 2\end{array}\right]$

Применение

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

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

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

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

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

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

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

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

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

Литература

• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Публикация
• Шаблон:Публикация