Алгоритм редукции решеточного базиса Ленстры – Ленстры – Ловаса - Lenstra–Lenstra–Lovász lattice basis reduction algorithm

В Ленстра – Ленстра – Ловас (LLL) алгоритм редукции базиса решетки это полиномиальное время редукция решетки алгоритм изобретенный Арьен Ленстра, Хендрик Ленстра и Ласло Ловас в 1982 г.^[1] Учитывая основа ${ displaystyle mathbf {B} = { mathbf {b} _ {1}, mathbf {b} _ {2}, dots, mathbf {b} _ {d} }}$ с п-мерные целочисленные координаты, для решетка L (дискретная подгруппа р^п) с ${ Displaystyle d Leq п}$, алгоритм LLL вычисляет LLL-уменьшенный (коротко, почти ортогональный ) базис решетки во времени

${ Displaystyle О (d ^ {5} п log ^ {3} B) ,}$

куда ${ displaystyle B}$ самая большая длина ${ displaystyle mathbf {b} _ {i}}$ по евклидовой норме, т. е. ${ displaystyle B = max left ( Vert mathbf {b} _ {1} Vert _ {2}, Vert mathbf {b} _ {2} Vert _ {2}, ..., Vert mathbf {b} _ {d} Vert _ {2} right)}$.^[2][3]

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

Снижение LLL

Точное определение LLL-редукции выглядит следующим образом. основа

${ displaystyle mathbf {B} = { mathbf {b} _ {1}, mathbf {b} _ {2}, dots, mathbf {b} _ {n} },}$

определить его Процесс Грама – Шмидта ортогональный базис

${ displaystyle mathbf {B} ^ {*} = { mathbf {b} _ {1} ^ {*}, mathbf {b} _ {2} ^ {*}, dots, mathbf {b } _ {n} ^ {*} },}$

и коэффициенты Грама-Шмидта

${ displaystyle mu _ {i, j} = { frac { langle mathbf {b} _ {i}, mathbf {b} _ {j} ^ {*} rangle} { langle mathbf { b} _ {j} ^ {*}, mathbf {b} _ {j} ^ {*} rangle}}}$, для любого ${ Displaystyle 1 Leq J <я Leq N}$.

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

1. (размер уменьшен) Для ${ Displaystyle 1 Leq J <я Leq п двоеточие влево | mu _ {я, J} вправо | Leq 0,5}$. По определению это свойство гарантирует уменьшение длины упорядоченного базиса.
2. (Условие Ловаса) Для k = 2,3, .., n ${ displaystyle двоеточие 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}}$.

Здесь, оценивая значение ${ displaystyle delta}$ параметра, можно сделать вывод, насколько хорошо сокращен базис. Высшие ценности ${ displaystyle delta}$ приводят к более сильным редукциям базиса. Первоначально А. Ленстра, Х. Ленстра и Л. Ловас продемонстрировали алгоритм LLL-редукции для ${ displaystyle delta = { frac {3} {4}}}$.Обратите внимание, что хотя LLL-редукция хорошо определена для ${ displaystyle delta = 1}$, полиномиальная сложность гарантируется только для ${ displaystyle delta}$ в ${ displaystyle (0,25,1)}$.

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

Приложения

Первым успешным применением алгоритма LLL было его использование Андрей Одлызко и Герман те Риле в опровержении Гипотеза Мертена.^[5]

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

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

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

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

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

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

Следующее описание основано на (Хоффштейн, Пайфер и Сильверман, 2008 г., Теорема 6.68) с исправлениями из опечаток.^[9]

ВХОД    решетчатая основа ${ displaystyle  mathbf {b} _ {0},  mathbf {b} _ {1},  ldots,  mathbf {b} _ {n}  in  mathbb {Z} ^ {m}}$    параметр ${ displaystyle  delta}$ с ${ Displaystyle { tfrac {1} {4}} < delta <1}$, Наиболее часто ${ displaystyle  delta = { tfrac {3} {4}}}$ПРОЦЕДУРА    ${ displaystyle  mathbf {B ^ { ast}}  получает { rm {GramSchmidt}} ( { mathbf {b} _ {0},  ldots,  mathbf {b} _ {n} }) =  { mathbf {b} _ {0} ^ { ast},  ldots,  mathbf {b} _ {n} ^ { ast} };}$  и не нормализовать    ${ displaystyle  mu _ {i, j}  получает { frac { langle  mathbf {b} _ {i},  mathbf {b} _ {j} ^ { ast}  rangle} { langle  mathbf {b} _ {j} ^ { ast},  mathbf {b} _ {j} ^ { ast}  rangle}};}$   используя самые актуальные значения ${ displaystyle  mathbf {b} _ {i}}$ и ${ displaystyle  mathbf {b} _ {j} ^ { ast}}$    ${ displaystyle k  получает 1;}$    пока ${ Displaystyle к  Leq п}$ делать        за ${ displaystyle j}$ из ${ displaystyle k-1}$ к ${ displaystyle 0}$ делать            если ${ displaystyle |  mu _ {k, j} |> { tfrac {1} {2}}}$ тогда                ${ displaystyle  mathbf {b} _ {k}  gets  mathbf {b} _ {k} -  lfloor  mu _ {k, j}  rceil  mathbf {b} _ {j};}$               Обновлять ${ displaystyle  mathbf {B ^ { ast}}}$ и связанные ${ displaystyle  mu _ {я, j}}$по мере необходимости.               (Наивный метод - пересчитать ${ displaystyle  mathbf {B ^ { ast}}}$ в любое время ${ displaystyle  mathbf {b} _ {i}}$ изменения:                ${ displaystyle  mathbf {B ^ { ast}}  получает { rm {GramSchmidt}} ( { mathbf {b} _ {0},  ldots,  mathbf {b} _ {n} }) =  { mathbf {b} _ {0} ^ { ast},  ldots,  mathbf {b} _ {n} ^ { ast} };}$)            конец, если        конец для        если ${ displaystyle  langle  mathbf {b} _ {k} ^ { ast},  mathbf {b} _ {k} ^ { ast}  rangle  geq  left ( delta -  mu _ {k, k-1} ^ {2}  right)  langle  mathbf {b} _ {k-1} ^ { ast},  mathbf {b} _ {k-1} ^ { ast}  rangle}$ тогда            ${ displaystyle k  получает k + 1;}$        еще            Замена ${ displaystyle  mathbf {b} _ {k}}$ и ${ displaystyle  mathbf {b} _ {k-1};}$            Обновлять ${ displaystyle  mathbf {B ^ { ast}}}$ и связанные ${ displaystyle  mu _ {я, j}}$по мере необходимости.            ${ Displaystyle к  получает  макс (к-1,1);}$        конец, если    конец пока    возвращаться ${ displaystyle  mathbf {B}}$ LLL сокращает базу ${ displaystyle  {b_ {0},  ldots, b_ {n} }}$ВЫХОД    сокращенная база ${ displaystyle  mathbf {b} _ {0},  mathbf {b} _ {1},  ldots,  mathbf {b} _ {n}  in  mathbb {Z} ^ {m}}$

Примеры

Пример из ${ displaystyle mathbf {Z} ^ {3}}$

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

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

то приведенный базис

${ displaystyle { begin {bmatrix} 0 & 1 & -1 1 & 0 & 0 0 & 1 & 2 end {bmatrix}}}$,

который уменьшен в размере, удовлетворяет условию Ловаса и, следовательно, является LLL-уменьшенным, как описано выше. См. W. Bosma.^[10] для получения подробной информации о процессе восстановления.

Пример из ${ Displaystyle mathbf {Z} [я] ^ {4}}$

Аналогичным образом, для базиса комплексных целых чисел, заданных столбцами матрицы ниже,

${ displaystyle { 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-сокращенный базис.

${ displaystyle { 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 как отдельная реализация
• ЗАЗОР как функция LLLReducedBasis
• Маколей2 как функция LLL в пакете LLLBases
• Магма как функции LLL и LLLGram (взяв матрицу грамма)
• Клен как функция IntegerRelations [LLL]
• Mathematica как функция РешеткаСнижение
• Библиотека теории чисел (NTL) как функция LLL
• PARI / GP как функция qflll
• Пиматген как функция analysis.get_lll_reduced_lattice
• SageMath как метод LLL управляемый fpLLL и NTL
• Изабель / ХОЛ в записи «Архив формальных доказательств» LLL_Basis_Reduction. Этот код экспортируется в эффективно исполняемый Haskell.^[11]

Смотрите также

• Медный метод

Примечания

Рекомендации

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