基本计算格问题：SVP、CVP 与 SIVP#

前置笔记：逐次极小值与 Minkowski 定理。

上一篇说明短向量的存在与长度界；本篇明确计算任务：输入什么、需要找到什么，以及“近似”如何衡量。

约定：输入格基 $B\in\mathbb Z^{m\times n}$ 列满秩，$\Lambda=\mathcal L(B)$，使用欧氏范数。CVP 还输入目标向量 $t\in\mathbb Q^m$。

使用整数或有理数输入，是为了能够用有限比特表示问题。有理输入可以通过统一缩放转为整数输入。近似因子记为 $\gamma=\gamma(n)\ge1$；$\gamma=1$ 对应精确求解，$\gamma$ 越大，对输出质量的要求越宽松 [1, pp. 9–10]。

#SVP：寻找一个最短非零格向量

最短向量问题（Shortest Vector Problem，SVP）：

给定 $B$，找到

$$v\in\Lambda\setminus\{0\}, \qquad \|v\|_2=\lambda_1(\Lambda).$$

其近似搜索版本 $\mathrm{SVP}_\gamma$ 要求找到

$$\boxed{ v\in\Lambda\setminus\{0\}, \qquad \|v\|_2\le\gamma\lambda_1(\Lambda) }.$$

“非零”条件不可省略，否则总可以输出 $0$。输出也不必是输入基中的某一列，它可以是基向量的任意非零整数线性组合 [1, pp. 9–10]。

#CVP：寻找距离目标最近的格向量

定义目标 $t$ 到格的距离：

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

最近向量问题（Closest Vector Problem，CVP）：

给定 $B,t$，找到

$$v\in\Lambda, \qquad \|t-v\|_2=\operatorname{dist}(t,\Lambda).$$

近似搜索版本 $\mathrm{CVP}_\gamma$ 要求找到

$$\boxed{ v\in\Lambda, \qquad \|t-v\|_2 \le\gamma\operatorname{dist}(t,\Lambda) }.$$

这里衡量的是到目标的距离，而非输出向量自身的长度；零向量也可以是合法答案。特别地，令 $t=0$ 时，CVP 的最优解就是 $0$，所以不能直接通过这一替换把 CVP 当作 SVP [2, pp. 7–8]。

#SIVP：寻找一组线性无关的短格向量

最短独立向量问题（Shortest Independent Vectors Problem，SIVP）的近似版本 $\mathrm{SIVP}_\gamma$：

给定 $B$，找到 $n$ 个线性无关格向量 $v_1,\ldots,v_n$，满足

$$\boxed{ \max_{1\le i\le n}\|v_i\|_2 \le\gamma\lambda_n(\Lambda) }.$$

它以 $\lambda_n$ 为基准，因为 $\lambda_n$ 是容纳 $n$ 个线性无关格向量所需的最小半径。

需要区分：

• 线性无关不等于原格的一组基。 输出向量可以只生成原格的一个真子格。
• 所有向量共用 $\lambda_n$ 这一长度基准。 即使 $\gamma=1$，也不要求逐个满足 $\|v_i\|_2=\lambda_i(\Lambda)$。

如果要求每个向量分别满足

$$\|v_i\|_2\le\gamma\lambda_i(\Lambda),$$

逐个约束各向量长度的任务对应逐次极小值问题（SMP），要求更强 [3, p. 10]。

#搜索、优化与判定：输出要求不同

以精确 SVP 为例：

• 搜索版本：输出一个最短非零格向量 $v$。
• 优化版本：求出最短长度 $\lambda_1(\Lambda)$。
• 判定版本：给定阈值 $r>0$，判断是否有 $\lambda_1(\Lambda)\le r$。

近似判定通常写成承诺问题 $\mathrm{GapSVP}_\gamma$。输入 $B$ 和正有理数 $r$，区分

$$\begin{cases} \text{YES},&\lambda_1(\Lambda)\le r,\\ \text{NO},&\lambda_1(\Lambda)>\gamma r. \end{cases}$$

若

$$r<\lambda_1(\Lambda)\le\gamma r,$$

输入落在承诺之外，算法无需给出规定的判定结果。

因此，$\mathrm{SVP}_\gamma$ 要求输出向量，$\mathrm{GapSVP}_\gamma$ 要求区分两类输入；讨论二者关系时需要说明具体归约 [1, pp. 9–10]。

类似地，$\mathrm{GapCVP}_\gamma$ 区分下式中的两种承诺情况 [1, p. 10]。

$$\operatorname{dist}(t,\Lambda)\le r \quad\text{and}\quad \operatorname{dist}(t,\Lambda)>\gamma r.$$

#沿用一个二维例子

取上一篇的格

$$\Lambda=\mathbb Z\times3\mathbb Z, \qquad \lambda_1=1,\quad\lambda_2=3.$$

三个搜索问题分别可以这样理解：

• SVP：输出 $(1,0)$，其长度为 $1$。
• CVP：若目标 $t=(2/5,13/5)$，则最近格点为 $(0,3)$，距离为 $2\sqrt2/5$。
• SIVP$_1$：输出 $(2,0)$ 和 $(0,3)$ 也合法。它们线性无关，最大长度为 $3=\lambda_2$。

最后一组向量生成的是

$$2\mathbb Z\times3\mathbb Z\subsetneq\Lambda,$$

并且长度分别为 $2,3$，没有逐个达到 $\lambda_1,\lambda_2$。这同时说明了 SIVP 对“格基”和“逐次最短”的两点区别。

#阅读位置

• SVP 与 CVP 可定义为搜索、优化、判定及相应近似版本，各版本具有不同的输出要求 [1, pp. 9–10]。
• SIVP 约束一组线性无关向量中的最大长度，SMP 则分别约束各个向量的长度 [3, p. 10]。
• CVP 以输出向量到目标的距离衡量解的质量 [2, pp. 7–8]。

接下来阅读格基约化与 LLL 算法，从什么样的基更利于寻找短向量开始，再连接正交化、尺寸约化和 Lovász 条件。

#参考文献