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

适用范围：计算格与格密码中的基本计算问题，使用欧氏范数。整理日期：2026-10-16。
前置笔记：[03 逐次极小值与 Minkowski 定理](/knowledge/successive-minima-and-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，第 9—10 页，§4]

## 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，第 9—10 页，Search SVP 与 Search SVP$_\gamma$]

## 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。[3，PDF 第 7—8 页，§5、Definition 9]

## 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），要求更强。[2，PDF 第 10 页，Definition 13、15]

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

以精确 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，第 9—10 页，§4]

类似地，$\mathrm{GapCVP}_\gamma$ 区分

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

[1，第 10 页，Promise CVP$_\gamma$]

## 沿用一个二维例子

取上一篇的格

$$
\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 对“格基”和“逐次最短”的两点区别。

## 来源与阅读位置

1. Oded Regev，*Lattices in Computer Science*，Lecture 1: *Introduction*，Fall 2004。主阅读位置为 §4、第 9—10 页，涵盖 SVP、CVP 的搜索、优化、判定与近似版本。[原文](https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/introduction.pdf)
2. Daniele Micciancio，*Minkowski's theorem*，PDF 页首标注 Fall 2017，由 2019 年课程页链接。PDF 第 10 页 Definition 13、15，补充 SIVP 与 SMP。[原文](https://cseweb.ucsd.edu/classes/fa19/cse206A-a/lec2.pdf)
3. Daniele Micciancio，*The dual lattice*，PDF 页首标注 Fall 2017，由 2019 年课程页链接。PDF 第 7—8 页 §5、Definition 9，对照 CVP 定义。[原文](https://cseweb.ucsd.edu/classes/fa19/cse206A-a/lec3.pdf)

来源于 2026-09-27 核对，正文按已确认的草稿整理。

下一篇计划：《05 格基约化与 LLL 算法》，从什么样的基更利于寻找短向量开始，再连接正交化、尺寸约化和 Lovász 条件。

## 引用此笔记

- [00 概览与阅读路线](/knowledge/lattices-overview/)
- [05 格基约化与 LLL 算法](/knowledge/lattice-reduction-and-lll/)
- [06 Babai 最近平面算法与近似 CVP](/knowledge/babai-nearest-plane/)
- [13 SIS 问题与短整数关系](/knowledge/sis-and-short-integer-relations/)