Уменьшение решетки
В математике цель сокращения базиса решетки состоит в том, чтобы найти базис с короткими, почти ортогональными векторами, когда в качестве входных данных задан целочисленный базис решетки . Это реализуется с помощью различных алгоритмов, время работы которых обычно не менее экспоненциально по размерности решетки.
Одной мерой почти ортогональности является дефект ортогональности . Это сравнивает произведение длин базисных векторов с объемом определяемого ими параллелепипеда . Для совершенно ортогональных базисных векторов эти величины будут одинаковыми.
Любой конкретный базис векторов может быть представлен матрицей , столбцы которой являются базисными векторами . В полномерном случае, когда количество базисных векторов равно размерности пространства, которое они занимают, эта матрица является квадратной, а объем фундаментального параллелепипеда является просто абсолютным значением определителя этой матрицы . Если количество векторов меньше размерности лежащего в основе пространства, то объем равен . Для данной решетки этот объем одинаков (с точностью до знака) для любого базиса и, следовательно, называется определителем решетки или постоянной решетки .
Дефект ортогональности представляет собой произведение длин базисных векторов на объем параллелепипеда;
Из геометрического определения можно понять, что с равенством тогда и только тогда, когда базис ортогонален.
Если задача редукции решетки определяется как поиск базиса с наименьшим возможным дефектом, то задача является NP - трудной . Однако существуют алгоритмы полиномиального времени для поиска базиса с дефектом, где c — некоторая константа, зависящая только от количества базисных векторов и размерности лежащего в основе пространства (если оно отличается) [ нужна ссылка ] . Это достаточно хорошее решение во многих практических приложениях .
