Ru.Wikipedia.Org - Алгоритм Ленстры — Ленстры

Меню
Главная
Случайная статья
Настройки

Алгоритм Ленстры — Ленстры — Ловаса
Материал из https://ru.wikipedia.org

Алгоритм Ленстры — Ленстры — Ловаса (ЛЛЛ-алгоритм, LLL-алгоритм) — алгоритм редукции базиса решётки^[англ.], разработанный Арьеном Ленстрой, Хендриком Ленстрой и Ласло Ловасом в 1982 году^[1]. За полиномиальное время алгоритм преобразует базис на решётке (подгруппе

\mathbb {R} ^{n}

) в кратчайший почти ортогональный базис на этой же решётке. По состоянию на 2019 год алгоритм Ленстры — Ленстры — Ловаса является одним из самых эффективных для вычисления редуцированного базиса в решётках больших размерностей. Он актуален прежде всего в задачах, сводящихся к поиску кратчайшего вектора решётки.

Содержание

История

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

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

\mathbb {R} ^{n}

процесс Грама Шмидта позволяет преобразовать произвольный базис в ортонормированный («идеал», к которому стремится ЛЛЛ-алгоритм). Но процесс Грама Шмидта не гарантирует того, что на выходе каждый из векторов будет целочисленной линейной комбинацией исходного базиса. Таким образом, полученный в результате набор векторов может и не являться базисом исходной решётки. Это привело к необходимости создания специального алгоритма для работы с решётками^[3].

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

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

Решётка в евклидовом пространстве — это подгруппа группы

(\mathbb {R} ^{n},+)

, порожденная

d

линейно независимыми векторами из

\mathbb {R} ^{n}

, называемыми базисом решётки. Любой вектор решётки может быть представлен целочисленной линейной комбинацией базисных векторов^[5]. Базис решётки определяется неоднозначно: на рисунке изображены два различных базиса одной и той же решётки.

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

1/2

)^[3].

Пусть в результате преобразования базиса

\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]}

), если он удовлетворяет следующим свойствам^[3]:

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

^[1].

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

Пусть

\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}

— сокращённый алгоритмом ЛЛЛ с параметром

\delta

базис на решётке

{\mathcal {L}}

. Из определения такого базиса можно получить несколько свойств

\mathbf {B}

. Пусть

\lambda _{1}({\mathcal {L}})

— норма кратчайшего вектора решётки, тогда:

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

Базис, преобразованный методом ЛЛЛ, почти самый короткий из всех возможных, в том смысле, что существуют абсолютные границы

c_{i}>1

такие, что первый базисный вектор не более чем в

c_{1}

раз длиннее самого короткого вектора решётки, аналогично, второй вектор базиса не более чем в

c_{2}

раз превосходит второй кратчайший вектор решётки и так далее (что прямо следует из свойства 1)^[6].

Алгоритм

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

базис решётки

\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\in \displaystyle \mathbb {R} ^{3}

(состоит из линейно независимых векторов),

параметр

\delta

{\textstyle {\frac {1}{4}}<\delta <1}

, чаще всего

{\textstyle \delta ={\frac {3}{4}}}

(выбор параметра зависит от конкретной задачи).

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

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

В алгоритме

\lfloor \mu _{k,j}\rceil

— округление по правилам математики. Процесс алгоритма, описанный на псевдокоде^[7]:

  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$ :
    для

Выходные данные: редуцированный базис:

\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)

битовых операций^[3].

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

X

). Но тогда операции будут производиться уже над целыми числами, не превышающими

X^{nd}

. В итоге будет максимум

O(d^{8}n^{4}\log ^{3}X)

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

\mathbb {R} ^{n}

, сложность алгоритма остается такой же, но увеличивается количество битовых операций. Так как в компьютерном представлении любое вещественное число заменяется рациональным в силу ограниченности битового представления, полученная оценка верна и для вещественных решёток^[3].

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

Пример

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

Пусть базис решётки

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

Примечания

¹ ² ³ ⁴ A. K. Lenstra, H. W. Lenstra Jr., L. Lovsz. Factoring polynomials with rational coefficients // Mathematische Annalen. — 1982. — С. 515—534. — ISSN 4. — doi:10.1007/BF01457454.
¹ ² The LLL Algorithm, 2010, 1 The History of the LLL-Algorithm.
¹ ² ³ ⁴ ⁵ ⁶ ⁷ Galbraith, Steven. 17. Lattice Reduction // Mathematics of Public Key Cryptography (англ.). — 2012. Архивировано 20 сентября 2015 года.
¹ ² Xinyue, Deng. An Introduction to LLL Algorithm (англ.) // Massachusetts Institute of Technology. — P. 9—10. Архивировано 8 декабря 2019 года.
Чередник И. В. Неотрицательный базис решетки (рус.) // 3-е изд. — Дискрет. матем., 2014. — Т. 26. — С. 127—135.
¹ ² Regev, Oded. Lattices in Computer Science: LLL Algorithm // New York University. Архивировано 20 марта 2021 года.
¹ ²
Nguyen, Phong Q., Stehl, Damien. Low-dimensional lattice basis reduction revisited (англ.) // ACM Transactions on Algorithms. — P. 1–48. — doi:10.1145/1597036.1597050.
Bosma, Wieb. 4. LLL // Computer Algebra. — 2007. Архивировано 8 мая 2019 года.
Shahriar Shahabuddin, Janne Janhunen, Zaheer Khan, Markku Juntti, Amanullah Ghazi. A customized lattice reduction multiprocessor for MIMO detection // 2015 IEEE International Symposium on Circuits and Systems (ISCAS). — 2015. — arXiv:1501.04860. — doi:10.1109/ISCAS.2015.7169312.
D. Simon. Selected applications of LLL in number theory // LLL+25 Conference. — Caen, France. Архивировано 6 мая 2021 года.
Abderrahmane, Nitaj. Cryptanalysis of NTRU with two public keys // International Association for Cryptologic Research. — Caen, France. Архивировано 21 декабря 2019 года.
Bleichenbacher, Daniel and May, Alexander. New Attacks on RSA with Small Secret CRT-Exponents // International Association for Cryptologic Research. — Darmstadt, Germany. Архивировано 24 июня 2021 года.
Liu, Jiayang, Bi, Jingguo and Xu, Songyan. An Improved Attack on the Basic Merkle–Hellman Knapsack Cryptosystems // IEEE. — Beijing 100084, China. Архивировано 17 июня 2021 года.
The LLL Algorithm, 2010, 4 Progress on LLL and Lattice Reduction.
The FPLLL development team. FPLLL, a lattice reduction library. — 2016. Архивировано 17 февраля 2020 года.
Integral matrices and lattices (неопр.). GAP. Дата обращения: 10 декабря 2019. Архивировано 19 декабря 2019 года.
LLLBases -- lattice reduction (Lenstra-Lenstra-Lovasz bases) (неопр.). Macaulay2. Дата обращения: 10 декабря 2019. Архивировано 10 декабря 2019 года.
LLL Reduction (неопр.). Magma. Дата обращения: 10 декабря 2019. Архивировано 10 декабря 2019 года.
IntegerRelations/LLL (неопр.). Maple. Дата обращения: 10 декабря 2019. Архивировано 18 сентября 2020 года.
LatticeReduce (неопр.). Wolfram Language Documentation. Дата обращения: 10 декабря 2019. Архивировано 10 декабря 2019 года.
MODULE:LLL (неопр.). NTL. Дата обращения: 10 декабря 2019. Архивировано 17 августа 2018 года.
Vectors, matrices, linear algebra and sets (неопр.). PARI/GP. Дата обращения: 10 декабря 2019. Архивировано 18 декабря 2019 года.
pymatgen.core.lattice module (неопр.). pymatgen. Дата обращения: 27 декабря 2019. Архивировано 18 декабря 2019 года.
Dense matrices over the integer ring (неопр.). sage. Дата обращения: 18 декабря 2019. Архивировано 6 мая 2021 года.

Литература

Huguette, Napias. A generalization of the LLL algorithm over euclidean rings or orders // J. The. Nombr. Bordeaux. — 1996. — doi:10.5802/jtnb.176.
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 Valle. — 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.