2. 格的基础数学

在进入格密码的具体构造之前，必须先把“格”这个几何对象本身讲清楚。格不是抽象的代数符号堆砌，而是一个可以在纸上画出来、可以用矩阵算出来、可以用几何量度量的离散点集。本节围绕五个核心概念展开：格的定义、基与格行列式、基本域、连续最小值，以及格与线性代数、几何之间的关联。理解这些内容，是后续分析 SVP、CVP 困难性以及参数安全性的前提。

一、格的定义：离散加法子群

设 n 维实向量空间 ℝⁿ 中有一组线性无关的向量 b₁, b₂, …, b_k（k ≤ n），则由它们的所有整系数线性组合构成的集合

ℒ = { z₁b₁ + z₂b₂ + … + z_kb_k : z_i ∈ ℤ }

称为由这组向量生成的格。当 k = n 时称为满秩格，密码学中绝大多数构造都工作在满秩格上。这个定义有两个关键点：系数必须是整数，向量必须线性无关。前者保证离散性——格点之间不会无限稠密；后者保证格不会退化成低维子空间。直观地说，格就是 ℝⁿ 中一个“规则排列、无限延伸”的点阵，类似把整数格 ℤⁿ 经过一个线性变换“拉伸、旋转”后得到的结果。

二、基与格行列式

把基向量按列排成矩阵 B = [b₁ | … | b_n]，则格可简写为 ℒ(B) = { Bz : z ∈ ℤⁿ }。同一个格有无穷多组基：若 U 是行列式为 ±1 的整数矩阵（幺模矩阵），则 BU 与 B 生成完全相同的格。这一点非常重要——它意味着“基”只是描述格的一种方式，而格本身是几何对象，不依赖于具体基的选择。

格的行列式定义为 det(ℒ) = |det(B)|。由于幺模变换不改变行列式的绝对值，这个量是格的不变量。几何上，det(ℒ) 等于格的基本平行多面体的体积，也等于格点在空间中“平均每个点占据的体积”。在密码学参数估计中，行列式直接决定了格点密度：det 越小，格点越密，短向量越容易出现，安全性相应下降。

三、基本域

给定基 B，其基本域（基本平行多面体）定义为

𝒫(B) = { Bx : x ∈ [0, 1)ⁿ }

也就是基向量的系数取半开区间 [0,1) 时扫出的区域。基本域的体积恰好等于 det(ℒ)。它的作用是把整个空间“铺满”：将基本域按所有格向量平移，可以得到空间的一个无重叠剖分，每个格点恰好对应一个平移副本。这正是“格点密度”的几何来源。需要注意，基本域依赖基的选择，不同基给出形状不同但体积相同的基本域；而格的 Voronoi 胞（最近点区域）则是与基无关的规范基本域，在分析 CVP 时更常用。

四、连续最小值

格的连续最小值 λ₁(ℒ) 定义为格中非零向量的最短欧氏长度，即 λ₁ = min{ ‖v‖ : v ∈ ℒ \ {0} }。更一般地，第 i 个连续最小值 λ_i 是使得存在 i 个线性无关格向量、且每个长度都不超过它的最小半径。λ₁ 刻画了格中“最短非零向量有多短”，是 SVP 的核心参数；λ₁ 越小，格越“容易”出现短向量，基于 SVP 的密码方案就越需要谨慎选择维度与模数。

一个常用的估计工具是高斯启发式（Gaussian heuristic）：随机格的最短向量长度大致满足 λ₁ ≈ √(n/(2πe)) · det(ℒ)^1/n。它把连续最小值与行列式、维度联系起来，是参数选取时快速判断“短向量是否异常短”的经验公式。需要强调，这是启发式估计，不是严格上界，实际安全性分析还要结合格基约化实验。

五、格与线性代数、几何的关联

格是线性代数与离散几何的交汇点。从线性代数看，格是 ℤⁿ 在矩阵 B 下的像，基变换对应幺模矩阵乘法，行列式是相似不变量，这些都与线性映射、子空间、秩等概念直接对应。从几何看，格是欧氏空间中的离散点集，长度、夹角、正交投影、凸包、Voronoi 剖分都是分析工具。SVP 问的是“格中离原点最近的非零格点”，CVP 问的是“给定目标点，格中哪个点离它最近”，两者都可以用几何语言精确表述。

实际分析中，我们常把“基的质量”与“格的安全性”区分开。一个格可能有一组非常“歪斜”的基，使得直接枚举短向量很困难；但通过格基约化（如 LLL、BKZ）可以把它变换成更“正交”的基，从而暴露短向量。因此，参数安全分析不能只看基矩阵长什么样，而要看格的行列式、维度、λ₁ 估计值以及约化算法的实际能力。下表给出一个便于快速对照的检查框架，用于在给定参数时判断需要关注哪些量。

把上述概念串起来：格由基生成，基的行列式绝对值给出格行列式，格行列式等于基本域体积并决定格点密度，格点密度与维度共同影响连续最小值 λ₁ 的典型尺度，而 λ₁ 正是 SVP 困难性与密码参数安全之间的桥梁。后续讨论具体格密码方案时，我们会反复回到这条链条上，用行列式和连续最小值来评估参数是否留有足够的安全裕度。