Уменьшение решетки

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

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

Почти ортогонально

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

Любое конкретное основание $n$ векторы могут быть представлены матрицей $B$, столбцы которого являются базисными векторами $b_{i},i=1,\ldots ,n$. В полномерном случае, когда число базисных векторов равно размерности занимаемого ими пространства, эта матрица является квадратной, а объем фундаментального параллелепипеда представляет собой просто абсолютное значение определителя этой матрицы. $\det(B)$. Если количество векторов меньше размерности основного пространства, то объем равен ${\sqrt {\det(B^{T}B)}}$. Для данной решетки $\Lambda$, этот объем одинаков (с точностью до знака) для любого базиса и поэтому называется определителем решетки $\det(\Lambda )$ или постоянная решетки $d(\Lambda )$.

Дефект ортогональности представляет собой произведение длин базисных векторов, деленное на объем параллелепипеда;

$\delta (B)={\frac {\Pi _{i=1}^{n}\|b_{i}\|}{\sqrt {\det(B^{T}B)}}}={\frac {\Pi _{i=1}^{n}\|b_{i}\|}{d(\Lambda )}}$

Из геометрического определения можно понять, что $\delta (B)\geq 1$ с равенством тогда и только тогда, когда базис ортогонален.

Если задача редукции решетки определяется как поиск базиса с наименьшим возможным дефектом, то задача является NP-трудной. . Однако существуют алгоритмы с полиномиальным временем для поиска базиса с дефектом. $\delta (B)\leq c$ где c — некоторая константа, зависящая только от количества базисных векторов и размерности основного пространства (если оно отличается) . Это достаточно хорошее решение для многих практических приложений. .

В двух измерениях

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

Псевдокод алгоритма, часто известный как алгоритм Лагранжа или алгоритм Лагранжа-Гаусса, выглядит следующим образом:

    Input: ${\textstyle (u,v)}$ a basis for the lattice ${\textstyle L}$. Assume that ${\textstyle ||v||\leq ||u||}$, otherwise swap them.
    Output: A basis ${\textstyle (u,v)}$ with ${\textstyle ||u||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$.

    While ${\textstyle ||v||<||u||}$:
         ${\textstyle q:=\lfloor {\langle u,{\frac {v}{||v||^{2}}}\rangle }\rceil }$ # Round to nearest integer
         ${\textstyle r:=u-qv}$
         ${\textstyle u:=v}$
         ${\textstyle v:=r}$

См. раздел об алгоритме Лагранжа в для получения более подробной информации.

Приложения

Алгоритмы сокращения решетки используются в ряде современных теоретико-числовых приложений, в том числе при открытии втулочного алгоритма для $\pi$. Хотя определение кратчайшего базиса, возможно, является NP-полной задачей, такие алгоритмы, как алгоритм LLL, может найти короткий (не обязательно самый короткий) базис за полиномиальное время с гарантированной производительностью в худшем случае. LLL широко используется в криптоанализе криптосистем с открытым ключом .

При использовании для поиска целочисленных отношений типичные входные данные алгоритма состоят из расширенного $n\times n$ единичная матрица с записями в последнем столбце, состоящими из $n$ элементы (умноженные на большую положительную константу $w$ наказывать векторы, сумма которых не равна нулю), между которыми ищется связь.

Алгоритм LLL для вычисления почти ортогонального базиса был использован, чтобы показать, что целочисленное программирование в любом фиксированном измерении может выполняться за полиномиальное время .

Алгоритмы

Следующие алгоритмы уменьшают базисы решетки; также перечислены несколько общедоступных реализаций этих алгоритмов.

Год	Алгоритм	Выполнение
1773	Редукция Лагранжа/Гаусса для двумерных решеток
1982	Ленстры – Ленстры – Ловаса Редукция	НТЛ , фпллл
1987	Block Korkine–Zolotarev	НТЛ , фпллл
1993	Сейсен Редукция