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

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

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

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

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

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

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

Из геометрического определения можно понять, что с равенством тогда и только тогда, когда базис ортогонален.

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

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

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

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

    Вход:  основа для решетки . Предположить, что , иначе поменяйте их местами. Выход: Основа  с .
    Пока :                                    


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

Приложения

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

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

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

Алгоритмы

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

ГодАлгоритмВыполнение
1773Редукция Лагранжа / Гаусса для двумерных решеток
1982Ленстра – Ленстра – Ловас снижениеNTL, fplll (ссылка на GitHub)
1987Блок Коркина Золотарева[4]NTL, fplll (ссылка на GitHub)
1993Сокращение Seysen[5]

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

  1. ^ Нгуен, Фонг К. (2009). «Постоянные и решеточные алгоритмы Эрмита». Алгоритм LLL. Берлин, Гейдельберг: Springer Berlin Heidelberg. С. 19–69. Дои:10.1007/978-3-642-02295-1_2. ISBN 978-3-642-02294-4. ISSN 1619-7100.
  2. ^ Ленстра, А.К.; Ленстра, Х. В., мл.; Ловас, Л. (1982). «Факторинг многочленов с рациональными коэффициентами». Mathematische Annalen. 261 (4): 515–534. CiteSeerX 10.1.1.310.318. Дои:10.1007 / BF01457454. HDL:1887/3810. МИСТЕР 0682664.CS1 maint: несколько имен: список авторов (связь)
  3. ^ Ленстра, Х.В. (1983). «Целочисленное программирование с фиксированным числом переменных». Математика. Опер. Res. 8 (4): 538–548. CiteSeerX 10.1.1.431.5444. Дои:10.1287 / moor.8.4.538.
  4. ^ Анро, Гийом; Стеле, Дэмиен (2008). "Наихудшие основания редуцированной решетки Эрмита-Коркина-Золотарева". arXiv:0801.3331 [math.NT].
  5. ^ Сейсен, Мартин (сентябрь 1993 г.). «Одновременное сокращение основы решетки и ее обратной основы». Комбинаторика. 13 (3): 363–376. Дои:10.1007 / BF01202355.