# 06 Babai 最近平面算法与近似 CVP

整理日期：2026-10-16。
前置笔记：[02 基本区域、格行列式与正交化](/knowledge/fundamental-region-and-orthogonalization/)、[04 基本计算格问题：SVP、CVP 与 SIVP](/knowledge/svp-cvp-and-sivp/)、[05 格基约化与 LLL 算法](/knowledge/lattice-reduction-and-lll/)。

本篇使用欧氏范数，先讨论满秩情形：

$$
B=(b_1,\ldots,b_n)\in\mathbb Z^{n\times n},
\qquad
\Lambda=\mathcal L(B),
\qquad
t\in\mathbb Q^n.
$$

记 $b_1^*,\ldots,b_n^*$ 为 Gram–Schmidt 正交化向量。

目标是找到 $v\in\Lambda$，使 $\|t-v\|$ 尽可能接近

$$
\operatorname{dist}(t,\Lambda)
=\min_{x\in\Lambda}\|t-x\|.
$$

## 1. 为什么叫“最近平面”

固定最后一个基向量的整数系数，可以把格分成若干层：

$$
\Lambda
=
\bigcup_{c\in\mathbb Z}
\left(
c b_n+\mathcal L(b_1,\ldots,b_{n-1})
\right).
$$

每一层位于一个仿射超平面

$$
H_c=c b_n+\operatorname{span}(b_1,\ldots,b_{n-1}).
$$

这些超平面互相平行，法向量为 $b_n^*$，相邻平面的距离为 $\|b_n^*\|$。因此，离 $t$ 最近的平面对应

$$
c_n
=
\operatorname{round}
\left(
\frac{\langle t,b_n^*\rangle}{\|b_n^*\|^2}
\right).
$$

算法先选这一层，再在该层中处理剩余的基向量，逐步把问题降到一维。

这里采用的是贪心选择：**最近的平面不一定包含最近的格点**，所以一般只能得到近似解。

## 2. 算法步骤

```text
NearestPlane(B, t):
    计算 B 的正交化向量 b₁*, …, bₙ*
    r ← t
    v ← 0

    对 i = n, n−1, …, 1:
        c ← round(〈r, bᵢ*〉 / ||bᵢ*||²)
        v ← v + c bᵢ
        r ← r − c bᵢ

    返回 v
```

其中 `round` 表示取最近整数；恰好位于中点时，固定采用一种取整规则即可。

理解算法时，需要区分两个操作：

- **计算系数使用 $b_i^*$**：利用正交方向判断当前目标离哪一层最近。
- **更新残差使用 $b_i$**：每次减去原格中的向量，保证最终输出仍属于 $\Lambda$。

每轮都对当前残差 $r$ 计算系数。按下标从大到小处理，是因为后续使用的 $b_1,\ldots,b_{i-1}$ 都与 $b_i^*$ 正交，不会改变已经处理好的这个方向。

最终

$$
v=\sum_{i=1}^n c_i b_i\in\Lambda,
\qquad
r=t-v.
$$

## 3. 任意基下的误差上界

每个正交方向都进行了一次最近整数取整，因此最终误差可以写成

$$
t-v=\sum_{i=1}^n\varepsilon_i b_i^*,
\qquad
|\varepsilon_i|\le\frac12.
$$

由正交性，

$$
\boxed{
\|t-v\|^2
\le
\frac14\sum_{i=1}^n\|b_i^*\|^2
}.
$$

这个结论对任意格基成立，但它给出的是由当前基决定的**绝对误差上界**，还没有说明误差相对最优距离有多大。相关几何解释和残差性质见 [Micciancio《Basis Reduction》，Fall 2017，§2，第 3–5 页，尤其 Lemma 5](https://cseweb.ucsd.edu/classes/fa19/cse206A-a/lec5.pdf)。

## 4. 配合 LLL 得到近似 CVP 算法

先使用第五篇的 LLL 算法约化输入基，再运行最近平面算法：

$$
B'\leftarrow \operatorname{LLL}_{3/4}(B),
\qquad
v\leftarrow\operatorname{NearestPlane}(B',t).
$$

得到

$$
\boxed{
\|t-v\|
\le
2^{n/2}\operatorname{dist}(t,\Lambda)
}.
$$

因此，这一组合是一个多项式时间的 $2^{n/2}$-近似 CVP 算法。这里固定 LLL 参数 $\delta=3/4$，复杂度按整数基和有理目标的输入位长计算。见 [Regev《Lecture 3: CVP Algorithm》，Fall 2004，第 1 页算法及第 3–4 页 Lemma 6](https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/cvp.pdf)。

近似保证的证明只需记住两个要点。

首先，LLL 条件给出

$$
\|b_i^*\|^2\le 2^{n-i}\|b_n^*\|^2,
$$

于是

$$
\sum_{i=1}^n\|b_i^*\|^2
\le
(2^n-1)\|b_n^*\|^2.
$$

其次，比较算法选中的层与一个最近格点所在的层：

- 如果处于同一层，就在这一层中递归分析。
- 如果处于不同层，最优距离至少为半个层间距，即 $\|b_n^*\|/2$。结合上面的误差上界，就能控制相对误差。

**LLL 控制正交化长度之间的关系，使逐层取整的误差能够与最优距离建立联系。**

## 5. 一个二维例子

沿用第二篇的基：

$$
b_1=(2,0),\qquad b_2=(1,2).
$$

其正交化向量为

$$
b_1^*=(2,0),\qquad b_2^*=(0,2).
$$

这组基本身已经满足 $\delta=3/4$ 的 LLL 条件。

取目标

$$
t=\left(\frac65,\frac9{10}\right).
$$

先处理第二个方向：

$$
c_2
=
\operatorname{round}
\left(
\frac{\langle t,b_2^*\rangle}{\|b_2^*\|^2}
\right)
=
\operatorname{round}\left(\frac9{20}\right)
=0.
$$

因此选中 $y=0$ 这一层，残差仍为 $t$。

再处理第一个方向：

$$
c_1
=
\operatorname{round}\left(\frac35\right)
=1.
$$

算法输出

$$
v=b_1=(2,0),
\qquad
\|t-v\|^2=\frac{29}{20}.
$$

但另一层中的格点 $b_2=(1,2)$ 满足

$$
\|t-b_2\|^2=\frac54<\frac{29}{20}.
$$

这说明：即使输入基已经经过 LLL 约化，最近平面算法仍可能错过真正的最近格点。

另外，若直接对原基坐标取整，

$$
B^{-1}t
=
\begin{pmatrix}
3/8\\
9/20
\end{pmatrix},
\qquad
B\,\operatorname{round}(B^{-1}t)=(0,0).
$$

它与最近平面算法的输出不同。两者的区别在于：直接坐标取整一次性处理原基坐标；最近平面算法沿正交方向，依据当前残差逐层取整。

LLL 提供基的质量保证，Babai 算法利用这组基逐层选取格点；二者结合，得到具有明确近似因子的 CVP 算法。

## 引用此笔记

- [00 概览与阅读路线](/knowledge/lattices-overview/)
- [07 对偶格与对偶基](/knowledge/dual-lattices/)
- [08 覆盖半径与转移定理](/knowledge/covering-radius-and-transference/)
- [16 投影格、BKZ 与局部 SVP](/knowledge/projected-lattices-bkz-and-local-svp/)