Поиск ближайшей точки в решётках

В этой учебно-обзорной статье представлен всесторонний обзор методов поиска ближайшей точки в решётках без регулярной структуры. Существующие стратегии поиска описаны в рамках единого подхода, а различия между ними разъяснены. Реализован эффективный алгоритм поиска ближайшей точки, основанный на варианте метода Pohst (1981), предложенном Schnorr и Euchner (1995). Для произвольной точки x ∈ ℝ^m и порождающей матрицы решётки Λ алгоритм вычисляет точку решётки Λ, ближайшую к x. Показано, что этот алгоритм значительно превосходит по скорости другие известные методы на основе теоретического сравнения с алгоритмом Kannan (1983, 1987) и экспериментального сравнения с алгоритмом Pohst (1981) и его вариантами, такими как декодер Viterbo–Boutros (см. там же, т. 45, с. 1639–1642, 1999). Разработаны модификации алгоритма для решения ряда связанных с решётками задач поиска, включая нахождение кратчайшего вектора, определение числа касания, вычисление векторов, релевантных в смысле Вороного (1908), и нахождение базиса, приведённого по Коркину–Золотарёву (1873).