最短向量问题

SVP 要在无限整数系数组合中找离原点最近的非零点。连续最优化会选择原点，逐列检查输入基又会遗漏由大系数抵消得到的短向量。困难性来自整数坐标的全局组合，而不是计算一个给定向量的长度。

基本区域体积保证短点存在，却不透露它落在哪个整数坐标。基若近乎平行，两个很长列向量之差可能极短；几何上显眼的候选与输入矩阵中显眼的列不再一致。格基约化试图恢复较好的坐标，但多项式时间保证通常只达到维数相关的近似因子。

SVP 的几何对象以原点为中心，因此与最近向量问题的任意目标不同。把目标设成零并不会得到 SVP：最近格点永远是零，正好被 SVP 的非零条件排除。

取

$|\det B|=1$，所以它生成 ${\mathbb{Z}}^2$。两列长度都约为 $100$，但

长度为 $1$，且整数格中没有长度介于 $0$ 与 $1$ 的非零向量，故它是精确最短解。这个例子展示的是抵消与表示质量，不是困难实例：二维中可直接计算。

另一最短向量 $(0,1)$ 在这个坏基下需要较大整数坐标：$-99b_1+100b_2=(0,1)$。因此只在小整数系数范围里枚举可能漏解；格点的几何长度和它相对当前基的系数大小不是同一尺度。

若算法输出 $(0,1)$，它也是精确解；SVP 通常不要求唯一。若输出长度 $\sqrt{2}$ 的 $(1,1)$，则是 $\sqrt{2}$-近似解，却不是精确解。只报告“找到了短向量”而不提供相对 ${\lambda }_1$ 的因子，无法对应任何标准近似保证。

范数也不能省略：${\ell }_1$、${\ell }_2$ 与 ${\ell }_{\mathrm{\infty }}$ 下的最短集合和归约常数可能不同。量子或经典最坏情形归约通常针对 GapSVP、SIVP 等特定近似问题，不能笼统改写成“精确 SVP 被归约”。

LLL 算法公理库LLL 格基约化LLL lattice basis reduction · Lenstra–Lenstra–Lovász algorithm · LLL 算法以整数列操作生成满足 size-reduction 与 Lovász 条件的同格基的多项式时间算法。通过格基约化给出维数指数级因子的多项式时间 SVP 近似：从 LLL-reduced 基的首向量可得依赖 $\delta$ 的保证，经典 $\delta =3/4$ 时常写为 $2^{(k-1)/2}{\lambda }_1$。LLL 只实现这一明确的近似变体，因此本页不在 metadata 中把它列作精确 SVP 的实现。

在有界距离解码公理库格上的有界距离解码Bounded distance decoding · BDD · 格有界距离解码在目标点到格的距离小于最短非零格向量长度的一定比例的承诺下，恢复其唯一最近格点的搜索问题。中，${\lambda }_1/2$ 决定最近格点的唯一半径。SIS、LWE 及其结构化变体的安全归约则常以近似 GapSVP 或 SIVP 的最坏情形困难性为起点；安全结论必须保留近似因子、维数增长和归约是经典还是量子。