适用范围：计算格与格密码中的基本计算问题，使用欧氏范数。整理日期：2026-10-16。 前置笔记：03 逐次极小值与 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\)，找到
其近似搜索版本 \(\mathrm{SVP}_\gamma\) 要求找到
“非零”条件不可省略，否则总可以输出 \(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\)，找到
近似搜索版本 \(\mathrm{CVP}_\gamma\) 要求找到
这里衡量的是到目标的距离，而非输出向量自身的长度；零向量也可以是合法答案。特别地，令 \(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\)，满足
它以 \(\lambda_n\) 为基准，因为 \(\lambda_n\) 是容纳 \(n\) 个线性无关格向量所需的最小半径。
需要区分：
- 线性无关不等于原格的一组基。 输出向量可以只生成原格的一个真子格。
- 所有向量共用 \(\lambda_n\) 这一长度基准。 即使 \(\gamma=1\)，也不要求逐个满足 \(\|v_i\|_2=\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\)，区分
若
输入落在承诺之外，算法无需给出规定的判定结果。
因此，\(\mathrm{SVP}_\gamma\) 要求输出向量，\(\mathrm{GapSVP}_\gamma\) 要求区分两类输入；讨论二者关系时需要说明具体归约。[1，第 9—10 页，§4]
类似地，\(\mathrm{GapCVP}_\gamma\) 区分
[1，第 10 页，Promise CVP\(_\gamma\)]
沿用一个二维例子#
取上一篇的格
三个搜索问题分别可以这样理解：
- 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,3\)，没有逐个达到 \(\lambda_1,\lambda_2\)。这同时说明了 SIVP 对“格基”和“逐次最短”的两点区别。
来源与阅读位置#
- Oded Regev，Lattices in Computer Science，Lecture 1: Introduction，Fall 2004。主阅读位置为 §4、第 9—10 页，涵盖 SVP、CVP 的搜索、优化、判定与近似版本。原文
- Daniele Micciancio，Minkowski’s theorem，PDF 页首标注 Fall 2017，由 2019 年课程页链接。PDF 第 10 页 Definition 13、15，补充 SIVP 与 SMP。原文
- Daniele Micciancio，The dual lattice，PDF 页首标注 Fall 2017，由 2019 年课程页链接。PDF 第 7—8 页 §5、Definition 9，对照 CVP 定义。原文
来源于 2026-09-27 核对，正文按已确认的草稿整理。
下一篇计划：《05 格基约化与 LLL 算法》，从什么样的基更利于寻找短向量开始，再连接正交化、尺寸约化和 Lovász 条件。