# 01 格与格基

适用范围：计算格与格密码的基础知识。整理日期：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]

在列向量作为基的约定下，以下操作保持格不变：

1. 交换两个基向量。
2. 将一个基向量取反。
3. $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$。

因此，一组向量即使线性无关且属于某个给定格，也未必是该格的基；还需要能够生成该格的全部点。

## 来源

1. Oded Regev，*Lattices in Computer Science*，Lecture 1: *Introduction*，Fall 2004，第 1 页定义 1—2、第 3 页定义 4 与引理 2—3、第 3—4 页引理 4。[原文](https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/introduction.pdf)
2. Daniele Micciancio，*Point Lattices*，PDF 页首标注 Fall 2017，由 2019 年课程页链接。PDF 第 2 页定义 1 与脚注 2、第 4 页定理 3、第 5 页基本列操作、第 7—8 页推论 10。[原文](https://cseweb.ucsd.edu/classes/fa19/cse206A-a/lec1.pdf)

两份来源于 2026-09-26 核对；正文按已确认的内容精简，矩阵反例为整理时的直接计算。

## 引用此笔记

- [00 概览与阅读路线](/knowledge/lattices-overview/)
- [02 基本区域、格行列式与正交化](/knowledge/fundamental-region-and-orthogonalization/)
- [07 对偶格与对偶基](/knowledge/dual-lattices/)
- [09 高斯函数与离散高斯分布](/knowledge/gaussian-functions-and-discrete-gaussians/)
- [12 q 元格与模线性方程](/knowledge/q-ary-lattices/)