适用范围：计算格与格密码的基础知识。整理日期：2026-09-26。
格与格基#
设 \(B=[b_1,\ldots,b_n]\in\mathbb R^{m\times n}\) 的列向量线性无关，则
\[
\mathcal L(B)=\{Bz:z\in\mathbb Z^n\}
\]
称为由 \(B\) 生成的格，\(B\) 是该格的一组基。格是点集，格基是生成它的一种表示。
- \(n\) 为格的秩，\(m\) 为环境维数；\(n=m\) 时称为满秩格。
- 整数限制针对组合系数，基向量和格点的坐标不必为整数。
- 线性空间 \(\operatorname{span}(B)=\{Bx:x\in\mathbb R^n\}\) 允许实数系数，格只允许整数系数。
- 基向量线性无关，因此每个格点在给定基下的整数坐标唯一。
不同资料对“维数”的用法不一致，本文统一区分“秩”与“环境维数”。[1，定义 1—2；2，定义 1 及脚注 2]
等价格基与换基#
同一个格可以有不同的基。对列满秩矩阵 \(B,B'\in\mathbb R^{m\times n}\)，
\[
\mathcal L(B')=\mathcal L(B)
\iff
B'=BU,\quad U\in\mathbb Z^{n\times n},\quad \det U=\pm1.
\]
这样的整数矩阵 \(U\) 称为幺模矩阵，其逆矩阵仍为整数矩阵。因此新旧基能相互通过整数线性组合得到，生成的格不变。[1，定义 4、引理 2—3；2，定理 3、推论 10]
在列向量作为基的约定下，以下操作保持格不变：
- 交换两个基向量。
- 将一个基向量取反。
- \(b_i\leftarrow b_i+k b_j\)，其中 \(k\in\mathbb Z\)、\(i\ne j\)。
任意两组等价格基都可以通过上述操作相互转换。后续格基约化正是在保持格不变的前提下，改善基向量的性质。[1，引理 4；2，第 2 节]
一个必要的辨析#
张成相同的实线性空间，不代表生成相同的格。
例如，\(I_2\) 与 \(\operatorname{diag}(2,1)\) 都张成 \(\mathbb R^2\)，但分别生成 \(\mathbb Z^2\) 与 \(2\mathbb Z\times\mathbb Z\)。后者无法通过整数系数生成 \((1,0)^T\)。
因此，一组向量即使线性无关且属于某个给定格，也未必是该格的基；还需要能够生成该格的全部点。
来源#
- Oded Regev，Lattices in Computer Science，Lecture 1: Introduction，Fall 2004，第 1 页定义 1—2、第 3 页定义 4 与引理 2—3、第 3—4 页引理 4。原文
- Daniele Micciancio，Point Lattices，PDF 页首标注 Fall 2017，由 2019 年课程页链接。PDF 第 2 页定义 1 与脚注 2、第 4 页定理 3、第 5 页基本列操作、第 7—8 页推论 10。原文
两份来源于 2026-09-26 核对；正文按已确认的内容精简，矩阵反例为整理时的直接计算。