Задача о кратчайшем векторе: различия между версиями

''Точечная решетка'' представляет собой множество всех целочисленных линейных комбинаций <math>\mathcal{L} (\mathbf{b}_1, ..., \mathbf{b}_n) = \Bigg\{ \sum_{i = 1}^n x_i \mathbf{b}_i : x_1, ..., x_n \in \mathbb{Z} \Bigg\}</math> из n линейно независимых векторов b1...bn2Rm в m-мерном евклидовом пространстве. Для удобства вычислений векторы решетки b1 bn часто предполагаются целыми (или рациональными), так что решетка может быть представлена целочисленной матрицей В = [b 1... , bn] 2 ZmX" (называемой базисом) с порождающими векторами в качестве столбцов. Используя матричную нотацию, точки решетки в L(B) удобно представить в виде Bx, где x – целочисленный вектор. Целые числа m и n называются размерностью и рангом решетки, соответственно. Заметим, что любая решетка допускает несколько базисов, но все они имеют одинаковые ранг и размерность.