Алгоритм приведения решеточного базиса Ленстры – Ленстры – Ловаса

Алгоритм Ленстра-Ленстра-Ловаса ( LLL ) сокращения базиса решетки — это с полиномиальным временем, сокращения решетки алгоритм изобретенный Арьеном Ленстра , Хендриком Ленстрой и Ласло Ловасом в 1982 году. Учитывая основу $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ с n -мерными целочисленными координатами для решетки L (дискретной подгруппы R ^н ) с $d\leq n$, алгоритм LLL вычисляет LLL-сокращенный (короткий, почти ортогональный ) базис решетки во времени $${\mathcal {O}}(d^{5}n\log ^{3}B)$$ где $B$ это наибольшая длина $\mathbf {b} _{i}$ по евклидовой норме , то есть $B=\max \left(\|\mathbf {b} _{1}\|_{2},\|\mathbf {b} _{2}\|_{2},\dots ,\|\mathbf {b} _{d}\|_{2}\right)$.

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

Снижение LLL

Точное определение LLL-reduced следующее: Учитывая основу $$\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{n}\},$$ определить его процесса Грама – Шмидта ортогональный базис $$\mathbf {B} ^{*}=\{\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\dots ,\mathbf {b} _{n}^{*}\},$$ и коэффициенты Грамма-Шмидта $$\mu _{i,j}={\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }},$$ для любого $1\leq j<i\leq n$.

Тогда основа $B$ является LLL-редуцируемым, если существует параметр $\delta$ в (0.25, 1] ​​такой, что выполнено следующее:

1. (уменьшенного размера) $1\leq j<i\leq n\colon \left|\mu _{i,j}\right|\leq 0.5$. По определению это свойство гарантирует сокращение длины упорядоченного базиса.
2. (условие коня) Для k = 2,3,..,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$ приводят к более сильному сокращению базиса. Первоначально А. Ленстра, Х. Ленстра и Л. Ловас продемонстрировали алгоритм LLL-редукции для $\delta ={\frac {3}{4}}$. Обратите внимание, что хотя LLL-редукция четко определена для $\delta =1$полиномиальная сложность гарантирована только для $\delta$ в $(0.25,1)$.

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

Приложения

Первым успешным применением алгоритма LLL было его использование Эндрю Одлыжко и Германом те Риле для опровержения гипотезы Мертенса .

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

В частности, алгоритм LLL образует ядро ​​одного из алгоритмов целочисленных отношений . Например, если считается, что r = 1,618034 является (слегка округленным) корнем неизвестного квадратного уравнения с целыми коэффициентами, можно применить сокращение LLL к решетке в $\mathbf {Z} ^{4}$ охватываемый $[1,0,0,10000r^{2}],[0,1,0,10000r],$ и $[0,0,1,10000]$. Первый вектор в сокращенном базисе будет целочисленной линейной комбинацией этих трех, поэтому обязательно имеет вид $[a,b,c,10000(ar^{2}+br+c)]$; но такой вектор «короток» только в том случае, если a , b , c малы и $ar^{2}+br+c$ еще меньше. Таким образом, первые три элемента этого короткого вектора, скорее всего, будут коэффициентами целого квадратичного многочлена которого является r , корнем . В этом примере алгоритм LLL находит кратчайший вектор [1, -1, -1, 0,00025] и действительно $x^{2}-x-1$ имеет корень, равный золотому сечению , 1,6180339887....

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

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

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

Псевдокод алгоритма LLL

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

INPUT
    a lattice basis b1, b2, ..., bn in Zm
    a parameter δ with 1/4 < δ < 1, most commonly δ = 3/4
PROCEDURE
    B* <- GramSchmidt({b1, ..., bn}) = {b1*, ..., bn*};  and do not normalize
    μi,j <- InnerProduct(bi, bj*)/InnerProduct(bj*, bj*);   using the most current values of bi and bj*
    k <- 2;
    while k <= n do
        for j from k−1 to 1 do
            if |μk,j| > 1/2 then
                bk <- bk − ⌊μk,j⌉bj;
               Update B* and the related μi,j's as needed.
               (The naive method is to recompute B* whenever bi changes:
                B* <- GramSchmidt({b1, ..., bn}) = {b1*, ..., bn*})
            end if
        end for
        if InnerProduct(bk*, bk*) > (δ − μ2k,k−1) InnerProduct(bk−1*, bk−1*) then
            k <- k + 1;
        else
            Swap bk and  bk−1;
            Update B* and the related μi,j's as needed.
            k <- max(k−1, 2);
        end if
    end while
    return B the LLL reduced basis of {b1, ..., bn}
OUTPUT
    the reduced basis b1, b2, ..., bn in Zm

Примеры

Пример из Z ³

Пусть решетчатый базис $\mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3}\in \mathbf {Z} ^{3}$, задается столбцами $${\begin{bmatrix}1&-1&3\\1&0&5\\1&2&6\end{bmatrix}}$$ тогда приведенный базис $${\begin{bmatrix}0&1&-1\\1&0&0\\0&1&2\end{bmatrix}},$$ который уменьшен по размеру, удовлетворяет условию Ловаса и, следовательно, уменьшен по LLL, как описано выше. См. В. Босма. для получения подробной информации о процессе сокращения.

Пример из Z[ i ] ⁴

Аналогично, для базиса комплексных целых чисел, заданных столбцами приведенной ниже матрицы, $${\begin{bmatrix}-2+2i&7+3i&7+3i&-5+4i\\3+3i&-2+4i&6+2i&-1+4i\\2+2i&-8+0i&-9+1i&-7+5i\\8+2i&-9+0i&6+3i&-4+4i\end{bmatrix}},$$ тогда столбцы приведенной ниже матрицы дают базис, уменьшенный с помощью LLL. $${\begin{bmatrix}-6+3i&-2+2i&2-2i&-3+6i\\6-1i&3+3i&5-5i&2+1i\\2-2i&2+2i&-3-1i&-5+3i\\-2+1i&8+2i&7+1i&-2-4i\\\end{bmatrix}}.$$

Реализации

LLL реализован в

• Арагели как функция lll_reduction_int
• fpLLL как отдельная реализация
• FLINT как функция fmpz_lll
• GAP как функция LLLReducedBasis
• Маколей2 как функция LLL в упаковке LLLBases
• Магма как функции LLL и LLLGram (берем грамм-матрицу)
• Клен как функция IntegerRelations[LLL]
• Mathematica как функция LatticeReduce
• Библиотека теории чисел (NTL) как функция LLL
• PARI/GP как функция qflll
• Пиматген как функция analysis.get_lll_reduced_lattice
• SageMath как метод LLL управляемый fpLLL и NTL
• Изабель/ХОЛ в записи «архива формальных доказательств» LLL_Basis_Reduction. Этот код экспортируется в эффективно исполняемый Haskell.

См. также

• Метод медника

Ссылки

• Напиас, Угетт (1996). «Обобщение алгоритма LLL на евклидовы кольца или порядки» . Journal de Théorie des Nombres de Bordeaux . 8 (2): 387–396. дои : 10.5802/jtnb.176 .
• Коэн, Анри (2000). Курс вычислительной алгебраической теории чисел . ГТМ. Том. 138. Спрингер. ISBN  3-540-55640-0 .
• Борвейн, Питер (2002). Вычислительные экскурсы по анализу и теории чисел . ISBN  0-387-95444-9 .
• Люк, Франклин Т.; Цяо, Саньчжэн (2011). «Поворотный алгоритм LLL» . Линейная алгебра и ее приложения . 434 (11): 2296–2307. дои : 10.1016/j.laa.2010.04.003 .
• Хоффштейн, Джеффри; Пайфер, Джилл; Сильверман, Дж. Х. (2008). Введение в математическую криптографию . Спрингер. ISBN  978-0-387-77993-5 .