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

Алгоритм Ленстра-Ленстра-Ловаса (ЛЛЛ) - алгоритм сокращения базиса решетки, изобретенный Арьеном Ленстра, Хендриком Ленстра и Ласло Ловасом в 1982 году. Алгоритм является основой проведения манипуляций с базисами на решетках в евклидовом пространстве.

Имея на входе базис целочисленных n-мерных векторов $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$, алгоритм, заданный на решетке (подгруппе Rⁿ ) с $\ d\leq 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)$. Изначально, алгоритм ЛЛЛ, работая за полиномиальное время, использовался для факторизации многочленов с целыми коэффициентами, для одновременного приближения действительных чисел рациональными, и для решения задачи целочисленного линейного программирования в пространстве фиксированной размерности.

Базис, сокращенный методом ЛЛЛ

Описание исходных данных и работы ЛЛЛ следующее: Пусть дан базис

$\mathbf {B} =\{\mathbf {b} _{0},\mathbf {b} _{1},\dots ,\mathbf {b} _{n}\},$

преобразованный с помощью процесса Грамма-Шмидта в ортогональный базис

$\mathbf {B} ^{*}=\{\mathbf {b} _{0}^{*},\mathbf {b} _{1}^{*},\dots ,\mathbf {b} _{n}^{*}\},$

с коэффициентами Грамма-Шмидта, определяемыми следующим образом

$\mu _{i,j}={\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}$, для всех $j,i$ таких, что $1\leq j<i\leq n$.

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

1. (Условие сокращения размера) Для всех $i,j$ таких, что $1\leq j<i\leq n\colon \left|\mu _{i,j}\right|\leq 0.5$. По определению это свойство гарантирует сокращение длины векторов упорядоченного базиса.
2. (Условие Ловаса) For k = 1,2,..,n $\colon \delta \Vert \mathbf {b} _{k-1}^{*}\Vert ^{2}\leq \Vert \mathbf {b} _{k}^{*}\Vert ^{2}+\mu _{k,k-1}^{2}\Vert \mathbf {b} _{k-1}^{*}\Vert ^{2}$.

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

Не существует алгоритма, который бы вычислял почти ортогональный базис с векторами наименьшей длины из возможных для базиса на решётке с размерностью более 4 за полиномиальное время. В то же время, базис, преобразованный методом ЛЛЛ, почти самый короткий из всех возможных, в том смысле, что существуют абсолютные границы $c_{i}>1$ такие, что первый базисный вектор не боле чем в $c_{1}$ раз длиннее чем самый короткий вектор решётки, аналогично, второй вектор базиса не более чем в $c_{2}$ раз превосходит второй кратчайший вектор решетки, и так далее.

Алгоритм ЛЛЛ

Следующее описание основано на (Hoffstein, Pipher & Silverman 2008, Теорема 6.68).

ВВОД:

$\triangleright$ базис решетки $b_{0},b_{1},\dots ,b_{n}\in Z^{m}$,

$\triangleright$ параметр $\delta$ c ${\frac {1}{4}}<\delta <1$, чаще всего $\delta ={\frac {3}{4}}$

ПРОЦЕСС:

   Выполнить процесса Грамма-Шмидта без нормировки:
   $ortho:=\mathrm {gramSchmidt} (\{b_{0},\dots ,b_{n}\})=\{b_{0}^{*},\dots ,b_{n}^{*}\}$
   Define $\scriptstyle \mu _{i,j}:={\frac {\langle b_{i},b_{j}^{*}\rangle }{\langle b_{j}^{*},b_{j}^{*}\rangle }}$, который должен всегда использовать самые последние значения $\scriptstyle b_{i},b_{j}^{*}$.
   Let $k=1$
   while $k\leq n$ do
       for j  from $k-1$ to 0 do
           if $|\mu _{k,j}|>{\frac {1}{2}}$ do
               $b_{k}=b_{k}-\lfloor \mu _{k,j}\rceil b_{j}$
               Обновить входные данные для ortho и все данные, зависящие от $\scriptstyle \mu _{i,j}$, если необходимо. 
               (Простой метод это пересчет $\scriptstyle ortho:=\mathrm {gramSchmidt} (\{b_{0},\dots ,b_{n}\})=\{b_{0}^{*},\dots ,b_{n}^{*}\}$ если $\scriptstyle b_{i}$ меняется.)
           end if
       end for
       if $\langle b_{k}^{*},b_{k}^{*}\rangle \geq (\delta -(\mu _{k,k-1})^{2})\langle b_{k-1}^{*},b_{k-1}^{*}\rangle$ then
           $k=k+1$
       else
           Поменять $\scriptstyle b_{k}$ и $\scriptstyle b_{k-1}$.
           Обновить входные данные для ortho и все данные, зависящие от $\scriptstyle \mu _{i,j}$, если необходимо. (См. выше комментарий.)
           $k=\max(k-1,1)$
       end if
   end while

ВЫВОД: Сокращенный методом ЛЛЛ базис: $b_{0},b_{1},\dots ,b_{n}$

Свойства уменьшенного базиса

Пусть $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{n}\}$ - сокращенный по алгоритму ЛЛЛ с параметром $\delta$ базис на решётке ${\mathcal {L}}$. Из определения такого базиса можно получить несколько свойств $\mathbf {B}$.

1. Первый вектор базиса не может быть сильно больше кратчайшего ненулевого вектора: $||\mathbf {b} _{1}||\leq (2/({\sqrt {4\delta -1}}))^{n-1}\cdot \lambda _{1}({\mathcal {L}})$. В частности, для $\delta =3/4$ получается $||\mathbf {b} _{1}||\leq 2^{(n-1)/2}\cdot \lambda _{1}({\mathcal {L}})$.
2. Первый вектор базиса ограничен определителем решетки: $||\mathbf {b} _{1}||\leq (2/({\sqrt {4\delta -1}}))^{(n-1)/2}\cdot (\det({\mathcal {L}}))^{1/n}$. В частности, для $\delta =3/4$ получается $||\mathbf {b} _{1}||\leq 2^{(n-1)/4}\cdot (\det({\mathcal {L}}))^{1/n}$.
3. Произведение норм векторов не может быть сильно больше определителя решетки: положим $\delta =3/4$, тогда $\prod _{i=1}^{n}||\mathbf {b} _{i}||\leq 2^{n(n-1)/4}\cdot \det({\mathcal {L}})$.

Пример

Следующий пример основывается на тексте Босма В.

ВВОД:

Пусть базис решетки $\mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3}\in Z^{3}$, задан столбцами матрицы:

${\begin{bmatrix}1&-1&3\\1&0&5\\1&2&6\end{bmatrix}}$

По ходу алгоритма ЛЛЛ получается следующее:

1. $b_{1}^{*}=b_{1}={\begin{bmatrix}1\\1\\1\end{bmatrix}},B_{1}=\langle b_{1}^{*},b_{1}^{*}\rangle ={\begin{bmatrix}1\\1\\1\end{bmatrix}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}=3$
2. For $i=2$ DO:
   1. For $j=1$ присвоить $\mu _{2,1}={\frac {\langle b_{2},b_{1}^{*}\rangle }{B_{1}}}={\frac {{\begin{bmatrix}-1\\0\\2\end{bmatrix}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}}{3}}={\frac {1}{3}}\left(<{\frac {1}{2}}\right)$ и $b_{2}^{*}=b_{2}-\mu _{2,1}b_{1}^{*}={\begin{bmatrix}-1\\0\\2\end{bmatrix}}-{\frac {1}{3}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}={\begin{bmatrix}{\frac {-4}{3}}\\{\frac {-1}{3}}\\{\frac {5}{3}}\end{bmatrix}}.$
   2. $B_{2}=\langle b_{2}^{*},b_{2}^{*}\rangle ={\begin{bmatrix}{\frac {-4}{3}}\\{\frac {-1}{3}}\\{\frac {5}{3}}\end{bmatrix}}{\begin{bmatrix}{\frac {-4}{3}}\\{\frac {-1}{3}}\\{\frac {5}{3}}\end{bmatrix}}={\frac {14}{3}}.$
3. $\mathbf {k} :=2$
4. Здесь 4 шаг алгоритма ЛЛЛ пропущен так как $\mu _{2,1}$ соответствует условию уменьшения размера
5. For $i=3$ и For $j=1,2$ вычислить $\mu _{i,j}$ и $B_{i}$: $\mu _{3,1}={\frac {\langle b_{3},b_{1}^{*}\rangle }{B_{1}}}={\frac {{\begin{bmatrix}3\\5\\6\end{bmatrix}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}}{3}}={\frac {14}{3}}(>{\frac {1}{2}})$ поэтому $b_{3}^{*}=b_{3}-\mu _{3,1}b_{1}^{*}={\begin{bmatrix}3\\5\\6\end{bmatrix}}-{\frac {14}{3}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}={\begin{bmatrix}{\frac {-5}{3}}\\{\frac {1}{3}}\\{\frac {4}{3}}\end{bmatrix}}$ и $\mu _{3,2}={\frac {\langle b_{3},b_{2}^{*}\rangle }{B_{2}}}={\frac {{\begin{bmatrix}3\\5\\6\end{bmatrix}}{\begin{bmatrix}{\frac {-4}{3}}\\{\frac {-1}{3}}\\{\frac {5}{3}}\end{bmatrix}}}{\frac {14}{3}}}={\frac {13}{14}}\left(>{\frac {1}{2}}\right)$ поэтому $b_{3}^{*}=b_{3}^{*}-\mu _{3,2}b_{2}^{*}={\begin{bmatrix}{\frac {-5}{3}}\\{\frac {1}{3}}\\{\frac {4}{3}}\end{bmatrix}}-{\frac {13}{14}}{\begin{bmatrix}{\frac {-4}{3}}\\{\frac {-1}{3}}\\{\frac {5}{3}}\end{bmatrix}}={\begin{bmatrix}{\frac {-18}{42}}\\{\frac {27}{42}}\\{\frac {-9}{42}}\end{bmatrix}}={\begin{bmatrix}{\frac {-6}{14}}\\{\frac {9}{14}}\\{\frac {-3}{14}}\end{bmatrix}}$ и $B_{3}=\langle b_{3}^{*},b_{3}^{*}\rangle ={\begin{bmatrix}{\frac {-6}{14}}\\{\frac {9}{14}}\\{\frac {-3}{14}}\end{bmatrix}}{\begin{bmatrix}{\frac {-6}{14}}\\{\frac {9}{14}}\\{\frac {-3}{14}}\end{bmatrix}}={\frac {126}{196}}={\frac {9}{14}}$
6. While $k\leq 3$ DO
   1. Сократить размер $b_{3}$ и скорректировать $\mu _{3,1}$ и $\mu _{3,2}$

      в соответствии с процедурой сокращения в 4 шаге: Для $\mid \mu _{3,1}\mid >{\frac {1}{2}}$ выполнить подпрограмму сокращения для (3,1):

      1. $r=\lfloor 0.5+\mu _{3,l}\rfloor =5$ и $b_{3}=b_{3}-5b_{1}={\begin{bmatrix}3\\5\\6\end{bmatrix}}-{\begin{bmatrix}5\\5\\5\end{bmatrix}}={\begin{bmatrix}-2\\0\\1\end{bmatrix}}$
      2. $\mu _{3,1}=\mu _{3,l}-r\mu _{1,1}={\frac {-1}{3}}\left(<{\frac {1}{2}}\right)$
      3. Присвоить $\mu _{3,1}=\mu _{3,1}-r={\frac {14}{3}}-5={\frac {-1}{3}}$

      For $\mid \mu _{3,2}\mid >{\frac {1}{2}}$ выполнить подпрограмму сокращения для (3,2):

      1. $r=\lfloor 0.5+\mu _{3,2}\rfloor =1$ и $b_{3}=b_{3}-b_{2}={\begin{bmatrix}3\\5\\6\end{bmatrix}}-{\begin{bmatrix}-1\\0\\2\end{bmatrix}}={\begin{bmatrix}4\\5\\4\end{bmatrix}}$
      2. Присвоить $\mu _{3,2}=\mu _{3,2}-r\mu _{2,2}={\frac {13}{14}}-1={\frac {-1}{14}}$
      3. $\mu _{3,2}=\mu _{3,2}-1={\frac {-1}{14}}\left(<{\frac {1}{2}}\right)$
   2. Так как $B_{3}<\left({\frac {3}{4}}-\mu _{3,2}^{2}\right)B_{2}$, следовательно:
      1. Поменять местами $b_{3}$ и $b_{2}$
      2. $k:=2$

Применить замену, продолжить исполнение алгоритма с базисом решетки, который задан следующим образом

${\begin{bmatrix}1&4&-1\\1&5&0\\1&4&2\end{bmatrix}}$

Повторить шаги алгоритма.

1. $b_{1}^{*}=b_{1}={\begin{bmatrix}1\\1\\1\end{bmatrix}},B_{1}=3$
2. $\mu _{2,1}={\frac {\langle b_{2},b_{1}^{*}\rangle }{B_{1}}}={\frac {{\begin{bmatrix}4\\5\\4\end{bmatrix}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}}{3}}={\frac {13}{3}}\left(>{\frac {1}{2}}\right)$
3. $b_{2}^{*}=b_{2}-\mu _{2,1}b_{1}^{*}={\begin{bmatrix}4\\5\\4\end{bmatrix}}-{\frac {13}{3}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}={\begin{bmatrix}{\frac {-1}{3}}\\{\frac {2}{3}}\\{\frac {-1}{3}}\end{bmatrix}}$.
4. $B_{2}=\langle b_{2}^{*},b_{2}^{*}\rangle ={\frac {2}{3}}$.
5. For $\mid \mu _{2,1}\mid >{\frac {1}{2}}$ выполнить подпрограмму сокращения для (2,1):
   1. $r=\lfloor 0.5+\mu _{2,l}\rfloor =4$ и $b_{2}=b_{2}-4b_{1}={\begin{bmatrix}4\\5\\4\end{bmatrix}}-{\begin{bmatrix}4\\4\\4\end{bmatrix}}={\begin{bmatrix}0\\1\\0\end{bmatrix}}$
   2. Set $\mu _{2,1}=\mu _{2,1}-4\mu _{1,1}={\frac {13}{3}}-4={\frac {1}{3}}\left(<{\frac {1}{2}}\right)$
6. Так как $B_{2}<\left({\frac {3}{4}}-\mu _{2,1}^{2}\right)B_{1}$, следовательно:
7. Поменять местами $b_{2}$ и $b_{1}$

ВЫВОД: базис, сокращенный методом ЛЛЛ

${\begin{bmatrix}0&1&-1\\1&0&0\\0&1&2\end{bmatrix}}$

Применение алгоритма

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

В частности, алгоритм ЛЛЛ формирует ядро алгоритмов поиска целочисленных решений. К примеру, зная, что r = 1.618034 это (округленный) корень полинома, неизвестное квадратное уравнение с целыми коэффициентами получить с помощью алгоритма ЛЛЛ уменьшения базиса решетки в $R^{4}$, порожденной векторами $[1,0,0,10000r^{2}],[0,1,0,10000r],$ and $[0,0,1,10000]$. Первый вектор в уменьшенном базисе будет целочисленной линейной комбинацией трех данных, поэтому будет обязательно представим в виде $[a,b,c,10000(ar^{2}+br+c)]$; но такой вектор будет коротким, только если a, b, c достаточно маленькие и $ar^{2}+br+c$ еще меньше. Поэтому первые три координаты полученного короткого вектора с большой вероятностью будут коэффициентами целочисленного квадратного полинома, у которого один из корней - r. В этом примере алгоритм ЛЛЛ в качестве результата выводит вектор [1, -1, -1, 0.00025], и, действительно, у $x^{2}-x-1$ есть корень, равный золотому сечению, 1.6180339887....

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

ЛЛЛ реализован в следующих функциях и методах:

• Arageli как функция lll_reduction_int
• fpLLL как автономная реализация
• GAP как функция LLLReducedBasis
• Macaulay2 as the function 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. — ISBN 3-540-55640-0.
• Borwein, Peter. Computational Excursions in Analysis and Number Theory. — 2002. — ISBN 0-387-95444-9.
• Luk, Franklin T.; Qiao, Sanzheng (2011). "A pivoted LLL algorithm". Lin. Alg. Appl. 434 (11): 2296—2307. doi:10.1016/j.laa.2010.04.003.
• Hoffstein, Jeffrey. An Introduction to Mathematical Cryptography / Jeffrey Hoffstein, Jill Pipher, J.H. Silverman. — Springer, 2008. — ISBN 978-0-387-77993-5.