格基

格基像一套可更换的整数坐标尺。剪切、交换方向或翻转方向不会改变可到达的格点；把某个方向放大两倍却会漏掉原来奇数层的点。因而“张成同一实空间”只回答方向是否齐全，“生成同一格”还要回答步长与整数网格是否完全一致。

基的几何质量差异可以很大。幺模变换能把短而近乎正交的基改成极长、几乎平行的向量，格点集合却一丝不变。许多格算法输入的是基，运行时间和近似质量会受这套表示影响；这不等于格的固有困难性随换基改变。

一个可复算的表示质量指标是正交亏格

不等式来自 Hadamard，等号恰在各列两两正交时成立。它会随幺模换基而改变，所以只能评价输入表示，不能作为格同构不变量；两个基即便亏格相近，也未必给格算法相同的 Gram–Schmidt 轮廓。

基本平行多面体 $\mathcal{P}(B)=B[0,1{)}^k$ 也随基变形，但它始终为 $V_{\mathrm{\Lambda }}/\mathrm{\Lambda }$ 提供一个基本区域。它的体积不随幺模换基改变，这一不变量正是格行列式理路格行列式Lattice determinant · Lattice covolume · 格余体积欧氏格基本平行多面体在其实张成空间中的内在体积。。

令 $B=I_2$ 生成 ${\mathbb{Z}}^2$，并取

$\det U=1$，而任意 $(a,b)\in {\mathbb{Z}}^2$ 可写成 $(a-2b)(1,0)+b(2,1)$，所以 $B^{\prime }$ 确为同一格的基。相反，$C=2I_2$ 的列也线性无关并张成 ${\mathbb{R}}^2$，却只生成 $2{\mathbb{Z}}^2$；其坐标变换行列式为 $4$，在 ${\mathbb{Z}}^2$ 中漏掉三个非零陪集。

即使每列都是格向量也不够。对 ${\mathbb{Z}}^2$，向量 $(1,1)$ 与 $(1,-1)$ 的行列式为 $-2$，只生成坐标奇偶性相同的点。这个子格在原格中的指数为 $2$，恰与行列式绝对值相符。两列长度均为 $\sqrt{2}$，该子格余体积为 $2$，所以其正交亏格恰为 $1$：它们是这个子格的好基，却仍不是 ${\mathbb{Z}}^2$ 的基。这说明几何质量检查不能替代整数生成检查。

Gram–Schmidt 正交化通常产生与 $B$ 张成同一实空间的正交向量，却一般不在 $\mathrm{\Lambda }$ 中，也不以整数系数生成 $\mathrm{\Lambda }$。格算法使用正交化结果估计长度和逐层舍入，但不能把它误认成新格基。具有 $k$ 列的秩亏矩阵更不是秩 $k$ 格的基：实坐标不唯一，按这 $k$ 列计算的 Gram 行列式为零。它的整数像可能是较低秩格，也可能不离散；即使是较低秩格，也应在其实际秩下重新选择基并计算余体积。

格基把无限点集压缩成有限矩阵，使成员判定、基本区域约化和对偶基计算成为线性代数问题。若 $B$ 是方阵且可逆，检查 $x\in \mathrm{\Lambda }$ 可计算 $B^{-1}x$ 是否为整数；低秩时则先验证 $x\in V_{\mathrm{\Lambda }}$，再用左逆求坐标。对 ${\mathbb{Z}}^n$ 的满秩整数子格，还可用 Hermite normal form 选出规范的三角表示；其对角元乘积给出指数。规范形适合判等与成员计算，却不保证列向量短或近乎正交，因此与格基约化承担不同任务。

坐标位长度也是算法输入的一部分。把 $b_2$ 替换成 $b_2+N{b}_1$ 是合法幺模换基，但会随 $N$ 增大输入整数和中间算术；任何“关于秩多项式时间”的说法若不计 $\log N$，都遗漏了标准位复杂度。

好基与坏基的差别催生了LLL 格基约化理路LLL 格基约化LLL lattice basis reduction · Lenstra–Lenstra–Lovász algorithm · LLL 算法以整数列操作生成满足 size-reduction 与 Lovász 条件的同格基的多项式时间算法。：它只施加幺模列变换，所以保留格，同时让 Gram–Schmidt 数据满足可控条件。密码构造常公开一个看似坏的基而把具有额外短性或采样能力的表示作为陷门；“两套基生成同一格”并不意味着从公开基高效恢复秘密基。