Русская Википедия:Алгоритм Ленстры — Ленстры — Ловаса

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Файл:Lattice-reduction.svg

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

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

История

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

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

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

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

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

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

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

<math display="inline">\mu_{i,j}=\frac{\langle\mathbf{b}_i,\mathbf{b}^*_j\rangle}{\langle\mathbf{b}^*_j,\mathbf{b}^*_j\rangle}</math>, для всех <math>j, i</math> таких, что <math>1 \leqslant j < i \leqslant d</math>.

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

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

Здесь <math>\|\mathbf{b}\|</math> — норма вектора, <math>\langle \mathbf{b}_i,\mathbf{b}^*_j \rangle</math> — cкалярное произведение векторов.

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

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

Пусть <math>\mathbf{B}=\{ \mathbf{b}_1,\mathbf{b}_2, \dots, \mathbf{b}_d \}</math> — сокращённый алгоритмом ЛЛЛ с параметром <math>\delta</math> базис на решётке <math>\mathcal L</math>. Из определения такого базиса можно получить несколько свойств <math>\mathbf{B}</math>. Пусть <math>\lambda_1(\mathcal L)</math> — норма кратчайшего вектора решётки, тогда:

1. Первый вектор базиса не может быть значительно длиннее кратчайшего ненулевого вектора:Шаблон:Pb<math display="inline">\|\mathbf{b}_1 \| \leqslant \left(\frac{2}{\sqrt{4\delta - 1}}\right)^{d-1} \cdot \lambda_1(\mathcal L)</math>. В частности, для <math>\delta = 3/4</math> получается <math>\|\mathbf{b}_1 \| \leqslant 2^{(d-1)/2} \cdot \lambda_1(\mathcal L)</math>.
2. Первый вектор базиса ограничен определителем решётки:Шаблон:Pb<math display="inline">\|\mathbf{b}_1 \| \leqslant \left(\frac{2}{\sqrt{4\delta - 1}}\right)^{(d-1)/2} \cdot \det(\mathcal L)^{1/d}</math>. В частности, для <math>\delta = 3/4</math> получается <math>\|\mathbf{b}_1 \| \leqslant 2^{(d-1)/4} \cdot (\det\mathcal L)^{1/d}</math>.
3. Произведение норм векторов не может быть сильно больше определителя решётки:Шаблон:Pb<math display="inline">\prod_{i=1}^d \|\mathbf{b}_i \| \leqslant \left(\frac{2}{\sqrt{4\delta - 1}}\right)^{d(d-1)/2} \cdot \det(\mathcal L)</math>. В частности, <math>\prod_{i=1}^d \|\mathbf{b}_i \| \leqslant 2^{d(d-1)/4} \cdot \det(\mathcal L)</math> для <math>\delta = 3/4</math>.

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

Алгоритм

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

базис решётки <math> \mathbf{b}_1, \mathbf{b}_2, \dots, \mathbf{b}_d \in \displaystyle\mathbb{R}^3</math> (состоит из линейно независимых векторов),

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

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

  Шаблон:Nowrap 
  (выполнить процесс Грама — Шмидта без нормировки);
  Шаблон:Nowrap всегда подразумевая Шаблон:Nowrap
  Шаблон:Nowrap
  Шаблон:Nowrap
    для Шаблон:Mvar Шаблон:Nowrap
       если <math display="inline">|\mu_{k,j}| > \frac{1}{2}</math>, то:
          Шаблон:Nowrap
          Обновить значения <math>|\mu_{k,j}|</math> для <math>j < k</math>;
       конец условия;
    конец цикла;
    Шаблон:Nowrap
       Шаблон:Nowrap
    иначе:
       Шаблон:Nowrap
       Обновить значения <math> \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</math> для <math>k>1</math>; <math> \mu_{k-1,j}, \mu_{k,j} </math> для <math>j < k </math>;
       <math>k = \max(k-1,1)</math>;
    конец условия;
  конец цикла.

Выходные данные: редуцированный базис: <math> \mathbf{b}_1, \mathbf{b}_2, \dots, \mathbf{b}_d </math>.

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

На входе имеется базис <math>n</math>-мерных векторов <math>\mathbf{B}=\{ \mathbf{b}_1,\mathbf{b}_2, \dots, \mathbf{b}_d \}</math> с <math> \ d \leqslant n </math>.

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

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

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

Пример

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

Пусть базис решётки <math> \mathbf{b}_1,\mathbf{b}_2, \mathbf{b}_3 \in \displaystyle\mathbb{Z}^{3}</math> (как подгруппа <math>(\R^n, +)</math>), задан столбцами матрицы:

<math>

\begin{bmatrix}

   1 & -1& 3\\
   1 & 0 & 5\\
   1 & 2 & 6

\end{bmatrix} </math>

По ходу алгоритма получается следующее: Шаблон:Ordered list=\frac{13}{14}\left(> \frac{1}{2}\right)</math>, тогда <math display=inline>b_{3}^{*}=\begin{bmatrix}\frac{-6}{14}\\\frac{9}{14}\\\frac{-3}{14}\end{bmatrix}</math> и <math display=inline>B_{3}= \frac{9}{14}</math> }} |При <math>k=2</math> имеем <math>\mu_{2,1} < \frac{1}{2}</math> и <math>(\delta - \mu_{2,1}^2) \| \mathbf{b}_{1}^*\|^2 \leqslant \| \mathbf{b}_2^* \|^2</math>, поэтому переходим к следующему шагу. |При <math>k=3</math> имеем: Шаблон:Ordered list |Теперь возвращаемся к шагу 1, при этом промежуточная матрица <math>(\mathbf{b}_1,\mathbf{b}_2, \mathbf{b}_3)</math> имеет вид <math> \begin{bmatrix}

   1 & 0& -1\\
   1 & 1 & 0\\
   1 & 0 & 2

\end{bmatrix} </math> }} Выходные данные: базис, редуцированный методом Ленстры — Ленстры — Ловаса:

<math>

\begin{bmatrix}

   0 & 1& -1\\
   1 & 0 & 0\\
   0 & 1 & 2

\end{bmatrix} </math>

Применение

Алгоритм часто применяется в рамках метода 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.

Литература

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