2.1 手算 SVP 与 CVP：二维小格枚举

2.1 手算 SVP 与 CVP：二维小格枚举

最短向量问题（SVP）：找格中长度非零最短的向量。最近向量问题（CVP）：找离任意目标点最近的格点。本节在一个行列式为 10 的二维小格上，把这两个问题各枚举一遍，看清朴素解法为何在小维度有效、在高维度必然破产。

承接第 1 章：我们已经会画格、会分辨好基坏基，现在把"找特殊点"正式立为计算问题——后面三章的加密、签名、同态，全部安全性都押在这两道题的难度上。本节是全章的几何起点，通往 2.2 节的代数化。

先动手：把半径 6 以内的格点一网打尽

继续用 1.2 节的格：b_1 = (4,1)，b_2 = (2,3)，行列式 10。SVP 的蛮力解法很直白：枚举所有整系数组合，量长度，取最短。先手工枚举长度平方不超过 36 的全部点（系数 i, j 各取 -3 到 3 已足够覆盖）：

枚举结果：最短非零向量是 (2,-2)，长度 \sqrt{8} \approx 2.83。你也可以反向核对一遍表里没有更短的漏网之鱼：任何系数绝对值都到 2 以上的组合，长度平方至少 2^2 \times 8 = 32 起步，不可能翻盘。

两把理论标尺可以给你的答案"体检"。Minkowski 上界保证最短向量不超过 2\,\det^{1/2}/\sqrt{\pi} = 2 \times 3.162 / 1.772 \approx 3.57，我们的 2.83 在界内。高斯启发式则估计最短向量"典型值"约为 \frac{\Gamma(2)}{\sqrt{\pi}} \cdot \sqrt{10} \approx 1.78——实际值 2.83 比典型值偏大，这是低维格的正常偏差，维数上百后启发式会越来越准（第 3 章估安全强度时它是主角）。

再撞一次墙：坏基上的 CVP

CVP 的场景：别人递给你一个不在格上的目标点 t，你找最近格点。取 t = (7,4)。延续 1.2 节的伏笔，把好基与坏基的"圆整法"结果并排摆出来。

好基 \{(4,1),(2,3)\}：解出系数 \alpha = 1.3、\beta = 0.9，四舍五入到 (1,1)，回代得候选点 (6,4)，距离平方 (7-6)^2 + (4-4)^2 = 1。坏基 \{(10,10),(22,23)\}：解出 \alpha = 7.3、\beta = -3，圆整到 (7,-3)，回代得 7 \times (10,10) - 3 \times (22,23) = (4,1)，距离平方 9 + 9 = 18。

哪边接近真相？对小格可以全员枚举验收。围绕圆整解搜索九宫格邻域，距离平方排名前三的候选是：(6,4) 距离平方 1；(8,2) 距离平方 (7-8)^2+(4-2)^2 = 5；(8,7) 与 (10,5) 并列 10。真解就是好基圆整给的 (6,4)，坏基答案偏了三倍多。下图把这一撞墙现场画了出来。

图：CVP 撞墙现场——目标点与最近格点

为什么枚举是死路：一笔指数账

二维能枚举，是因为半径内的候选点少；维数一高，候选点数量按体积膨胀。半径 r 的球在 n 维格里约能容纳 \frac{v_n r^n}{\det} 个格点（v_n 为单位球体积）。即使只枚举半径 \sqrt{2}\,\lambda_1 内的点，复杂度也是 2^{\Theta(n)}：具体量级上，目前最好的枚举算法在维数 60 的随机格上就要耗到天量操作，而第 7 章你会在 Kyber 的参数里看到 实用格的维数是 512 起步。维数，就是格密码的护城河。

顺带把"难"说精确：SVP 已被证明在近似因子接近常数时是 NP 难的，CVP 更早就被证明 NP 难；密码学用的是它们的"间隙"版本（GapSVP）——判定"最短向量不超过 d"还是"超过 g \cdot d"，g 是间隙。这些名字会在第 3 章的归约链条里反复出现，此处先混个脸熟。

代码：把枚举写成三十秒实验

import numpy as np
from itertools import product

B = np.array([[4, 1], [2, 3]])          # 行 = 基向量
t = np.array([7, 4])                    # CVP 目标

best = None
for coef in product(range(-4, 5), repeat=2):
    v = np.array(coef) @ B
    d2 = int((t - v) @ (t - v))
    if best is None or d2 < best[1]:
        best = (tuple(v), d2)

print("最近格点:", best[0], " 距离平方:", best[1])   # (6, 4) 1

# SVP：非零最短
cands = sorted({tuple(c @ B) for c in product(range(-5, 6), repeat=2)})
sv = min((v for v in cands if v != (0, 0)), key=lambda v: v[0]**2 + v[1]**2)
print("最短向量:", sv, " 长度平方:", sv[0]**2 + sv[1]**2)   # (2, -2) 8
​

跑完顺手做个变式：把 B 换成坏基 [[10,10],[22,23]]，枚举结果不变（真解还是 (6,4)），但圆整法会翻车——枚举不挑基，圆整法挑。这个反差正是第 6 章"规约算法寻找好基"的全部动机。

问题：枚举半径取多大才算数

动手时容易在半径的选择上犯嘀咕。判据来自理论：最短向量长度 \lambda_1 满足 Minkowski 上界，枚举半径只要取到该上界就必然覆盖真解，本例即 3.57，取 6 留足冗余。高维情形枚举半径由启发式估计给出，代价是候选数量按半径的维数次方膨胀——这也是为什么半径选择在高维变成了一门与剪枝策略联动的手艺，第 6 章的投影枚举会正式处理它。

问题：CVP 的"最近"唯一吗

本例 (6,4) 独占距离平方 1，答案唯一。但格的对称性允许平局：把目标挪到基本域的正中心（Voronoi 胞腔的深洞），最近的格点可以并列多个。密码学解密时平局是灾难——两个"最近"意味着两份合法明文，所以实战方案都会把参数调到让目标点远离一切平局区，解密失败率的计算（第 4 章 Kyber 参数表里的那行）正是在数这类边界事件的发生概率。

要点速记：SVP 与 CVP 是格密码安全性的两块基石；二维枚举可信，高维枚举复杂度指数爆炸；圆整法是好基专属的捷径；"维数换安全"是整本教程的第一条工程定律。

下一节把这两道几何题翻译成线性代数的语言——给方程组撒上误差，LWE 登场。