1.1 十分钟画出一个格

1.1 十分钟画出一个格

格（lattice） 是 n 维空间中由一组基向量的整系数组合生成的全部点构成的离散点阵。本节不急着背定义，而是先在坐标纸上画出你的第一个格，数一数它的格点，量一量它的基本域面积，然后用代码复现这一切——做完这十分钟的练习，定义反而变成了水到渠成的一行字。

上一章导读里我们说这本教程"先算再看后推"，现在就从这个承诺兑现起。你需要的东西只有两样：一张坐标纸，一支笔。承上启下地说：本章画出的这个格，会在第 2 章变成困难问题的实验台，在第 6 章变成攻击算法的试金石。

动手：两个向量，张出一片点阵

在坐标纸上取定两个向量：

现在定义一个操作：取任意整数系数 z_1, z_2 \in \mathbb{Z}，构造 z_1 b_1 + z_2 b_2。注意关键词是整数——系数不允许是 0.5、不允许是 \sqrt{2}，只能是 \ldots, -2, -1, 0, 1, 2, \ldots。把所有能这样构造出来的向量都标在图上：

• z_1=1, z_2=0：得 (2,0)；
• z_1=0, z_2=1：得 (1,2)；
• z_1=1, z_2=1：得 (3,2)；
• z_1=-1, z_2=2：得 (0,4)；
• z_1=3, z_2=-1：得 (5,-2)。

标出几十个之后，纸上会出现一片间隔规整但行不对齐坐标轴的点阵：每一行都向右上倾斜两格。这片点阵就是由 \{b_1, b_2\} 张成的格，记作 \mathcal{L}(b_1, b_2)。把你的手工结果与下图对照——如果你画的行倾斜方向和斜率一致，你就已经"会画格"了。

图：基 b1=(2,0) 与 b2=(1,2) 张成的二维格

现在把定义写严：给定 n 个线性无关的向量 b_1, \ldots, b_n \in \mathbb{R}^n，它们张成的格是

向量组 B 叫作这个格的基。两个约束各就各位：线性无关保证张成的空间维数等于向量个数，整系数保证点阵离散——实系数组合会把整片空间填满，不留任何"格"的味道。格是无限点阵，我们画的是它的一个窗口。

基本域：给格量面积

回到坐标纸。取 b_1 与 b_2 为两条边拼出的平行四边形，它的四个顶点是 (0,0)、(2,0)、(3,2)、(1,2)。这个平行四边形叫基本域：把无数个它的平移副本铺满全平面，每个副本里恰好落着一个格点。基本域的面积有公式可算，就是基向量组排成矩阵的行列式的绝对值：

你可以在图上验证：那个平行四边形底为 2、高为 2、面积为 4，而每 4 个单位面积里恰好有一个格点。格行列式是格的"密度倒数"——这个数字在密码学里无处不在：密文尺寸、安全强度估算、最短向量长度的理论上界，全都要拿行列式开刀。第 3 章的强度估算和第 7 章的参数对照表里，它会反复登场。

亲手验证：基可以换，格不变

在原格上任取两个点，比如 c_1 = (3,2) 和 c_2 = (2,0)，问：用 \{c_1, c_2\} 当基，能张出同样的点阵吗？用整系数组合试几个点：c_1 - c_2 = (1,2)，正是原来的 b_2；c_2 = b_1。两个老基都能由新基整系数表出，所以新基张成的点阵是老点阵的子集；反过来 b_1, b_2 也能被 c_1, c_2 整系数表出，子集关系倒过来也成立——两个集合相等。判断一个候选基组合法的通用判据是：把新旧基的系数关系排成矩阵 U，U 的元素全为整数且行列式等于 \pm 1（这样的矩阵叫幺模矩阵）。本例中 c_1 = b_1 + b_2、c_2 = b_1，系数矩阵 \begin{pmatrix}1&1\\1&0\end{pmatrix} 的行列式是 -1，合法。

一个格有无穷多组基，但行列式不变——行列式是格本身的属性，不是基的属性。

用代码复现你画的一切

把上面的手工过程写成十几行 Python，跑出来的点集应当与你纸上标的完全一致：

import numpy as np

B = np.array([[2, 0],
              [1, 2]])          # 两行 = 两个基向量

# 1) 枚举 i, j 在 [-3, 3] 的全部格点
points = [(i, j) @ B for i in range(-3, 4) for j in range(-3, 4)]

# 2) 基本域面积 = 行列式绝对值
area = abs(round(np.linalg.det(B)))
print("基本域面积:", area)        # 输出: 4

# 3) 验证新基 c1=(3,2), c2=(2,0) 张出同一个格
C = np.array([[3, 2],
              [2, 0]])
U = np.linalg.inv(C.T) @ B.T      # 老基用新基表出的系数
print("系数矩阵:\n", np.round(U)) # 输出: [[0. 1.], [1. 1.]]（全为整数）
print("幺模判定 det:", round(np.linalg.det(np.round(U).astype(int))))  # 输出: -1
​

三段代码各对应本节一个知识点：格点的枚举、行列式即面积、幺模变换换基。建议把 B 换成 (4,1)、(2,3) 再跑一遍——那是下一节的主角。

为什么密钥是一组数，安全是一个几何问题

现在可以回答一个工程问题：格密码的密钥长什么样？答案：就是一组基向量。第 4 章你会看到 Kyber 的私钥本质上是一小段带噪声的格基信息，公钥是它的一个"劣化版本"。而攻击者的任务——无论包装成解密、伪造还是求逆——几何上全都是同一类问题：在点阵里找特殊的点（最短的那个、离目标最近的那个）。问题越具体越好攻击，所以格密码的安全性直接取决于：给定一个格，找它的好基有多难。这正是第 2 章要正式定义的困难问题。

本节要点回顾：格由基的整系数组合生成，离散性来自整数约束；基本域面积等于行列式，是格的固有属性；换基必须走幺模矩阵，格不变而基有无穷多；格密码的密钥是基，安全性是几何问题。

下一节我们把这些工具对准一个刁钻的事实：用"坏基"做同样的事，一切都会变得面目全非。