Редукция решетки

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

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

Почти ортогональный [ править ]

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

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

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

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

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

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

В двух измерениях [ править ]

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

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

 Вход: основа решетки . Предположим, что в противном случае поменяйте их местами.${\textstyle (u,v)}$${\textstyle L}$${\textstyle ||v||\leq ||u||}$ Выход: Основа с .${\textstyle (u,v)}$${\textstyle ||u||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$

 Пока : ${\textstyle ||v||\leq ||u||}$${\textstyle q:=\lfloor {\langle u,{\frac {v}{||v||^{2}}}\rangle }\rceil }$ ${\textstyle r:=u-qv}$ ${\textstyle u:=v}$ ${\textstyle v:=r}$

См. Подробности в разделе об алгоритме Лагранжа в ^[1] .

Приложения [ править ]

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

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

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

Алгоритмы [ править ]

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

Ссылки [ править ]