# 17 筛法的基本框架与两向量约化

整理日期：2026-10-16。  
适用范围：欧氏格上的两向量筛法、向量池维护，以及局部约化、运行成本和停止条件的区别。  
前置笔记：[15 高斯启发式与随机球面模型](/knowledge/gaussian-heuristic-and-random-spheres/)、[16 投影格、BKZ 与局部 SVP](/knowledge/projected-lattices-bkz-and-local-svp/)。

设当前处理的格为 $\Lambda=\mathcal L(C)$，秩为 $s$，使用欧氏范数。在 BKZ 中，$\Lambda$ 可以是第 16 篇的局部投影格；这里的 $s$ 始终表示实际筛法维数。

## 1. 筛法维护什么

筛法维护一个非零格向量池

$$
D\subseteq\Lambda\setminus\{0\},
\qquad N=|D|,
$$

通过已有向量的加减产生较短候选，并持续调整池中的向量。

基本代数依据是格对整数线性组合封闭。若

$$
x=Cz_x,\qquad y=Cz_y,
\qquad z_x,z_y\in\mathbb Z^s,
$$

则

$$
x\pm y=C(z_x\pm z_y)\in\Lambda.
$$

因此，约化时可以同步更新整数系数；在投影格中计算时，这些系数也用于后续提升。

向量池可以包含大量线性相关向量，不要求它构成格基。如果只对初始池中的向量反复加减，所有结果都留在初始池生成的子格中；补充新样本可以改变这一搜索范围。

筛法的理论起点是 AKS 随机算法。它通过覆盖与反复缩短控制长度，再利用随机扰动分析非零短向量出现的概率，得到 $2^{O(s)}$ 乘输入长度多项式的时间界。仅证明“向量不断变短”还不够，因为它们可能归零。参见 [Regev，Fall 2004，Lecture 8，Lemma 2 及后续正确性分析，PDF 第 1–4 页](https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/svpalg.pdf)。

以下先讨论直接处理格向量的基本操作；AKS 和原始 ListSieve 的扰动结构在具体算法中再展开。

## 2. 两向量约化的判据

给定非零向量 $x,y$，同时考虑加法和减法，有

$$
\min_{\sigma\in\{-1,1\}}\|x-\sigma y\|^2
=
\|x\|^2+\|y\|^2-2|\langle x,y\rangle|.
$$

因此，**用 $y$ 缩短指定向量 $x$**的条件是

$$
\boxed{
\min_{\sigma\in\{-1,1\}}\|x-\sigma y\|<\|x\|
\iff
2|\langle x,y\rangle|>\|y\|^2.
}
$$

若成立，选择使内积项被减去的符号，将 $x$ 更新为 $x-\sigma y$。本篇只使用系数为 $\pm1$ 的加减操作。

若允许替换两条向量中较长的一条，条件则为

$$
\boxed{
\min\{\|x-y\|,\|x+y\|\}
<
\max\{\|x\|,\|y\|\}.
}
$$

这两个判据的比较对象不同：前者固定被约化的向量，后者先选择较长者。

对于等长向量 $\|x\|=\|y\|=R$，条件退化为第 15 篇的

$$
|\cos\theta|>\frac12.
$$

长度不同时，使用上面的内积判据即可，无须把阈值固定为 $60^\circ$。基本操作采用严格变短条件；等长替换若要允许，需要额外的规则。

若结果为零，应将其丢弃并记录为碰撞；零向量不能作为 SVP 的解。一次操作中产生零，意味着当前两条向量相等或互为相反数；连续约化后归零则可能反映更一般的整数关系。

## 3. 用固定向量池约化一个候选

先把 $D$ 固定，只约化输入向量 $v$。下面是根据上一节判据写出的基础子程序：

~~~text
Reduce(v, D):
    反复执行：
        如果 v = 0：
            返回 0

        扫描 D，寻找满足 2·|〈v,u〉| > ||u||² 的向量 u
        如果不存在这样的 u：
            返回 v

        σ ← 1（若 〈v,u〉 ≥ 0），否则 −1
        v ← v − σ·u
        # v 已改变，下一轮重新检查 D
~~~

需要重新检查，是因为用一条向量缩短 $v$ 后，它可能又能被此前检查过的其他向量缩短。

在精确运算下，这个子程序会终止：每次更新都严格减小长度，而初始半径内的格点只有有限个。这个论证只给出有限终止性，没有给出高效的迭代次数界。

返回非零向量时，得到的是“相对于当前固定池，无单次加减可以继续缩短”。它不保证该向量是全格最短向量，也不保证换用另一组约化顺序会得到相同结果。

列表约化及引入缩短因子来控制迭代次数的讨论，见 [Micciancio《Sieving Algorithms for Exact SVP》，正文标注 Fall 2021，§2.2.2，Figure 2，PDF 第 3–4 页](https://cseweb.ucsd.edu/classes/fa25/cse206A-a/LecSieve.pdf)。本节伪代码省略了原始 ListSieve 的扰动与缩短因子，只表示直接格向量上的基本操作。

## 4. 从候选约化到完整向量池

完整筛法还需要决定：候选从哪里来，约化结果如何进入池，旧向量是否重新处理，以及何时停止。

采样器应说明输出分布、长度范围和对输入基的依赖。随机选择整数系数再乘以基，并不会自动得到球内均匀样本或球面均匀方向。

两种典型组织方式是：

- **批量缩短。** 从一批长度至多为 $R$ 的向量出发，选取中心，用相近向量减去中心，构造长度至多为 $\gamma R$ 的下一批，其中 $0<\gamma<1$。池大小可能随轮次减少，需要同时分析中心消耗与零向量损失。
- **增量维护。** 逐个处理新样本或待处理向量，用当前池约化候选，再将非零结果插入。若新向量还能缩短旧向量，就把受影响的旧向量移出，其约化结果进入待处理队列，稍后重新检查。

批量结构可对照 [Nguyen–Vidick，2008，作者稿 §4.1，Algorithms 4–5，PDF 第 13–14 页](https://people.csail.mit.edu/vidick/JoMC08.pdf)；增量结构与旧向量回收可对照 [Micciancio–Voulgaris，SODA 2010，作者稿 19 页版，§3.2，Algorithm 2，PDF 第 8–9 页](https://cseweb.ucsd.edu/~daniele/papers/Sieve.pdf)。

两类结构都利用向量相减，但并非每一步都调用上一节的 Reduce。批量算法按本轮目标半径组织输出；增量算法则需要维护当前池与待处理队列之间的关系。

更新规则也会影响代数性质：保留 $y$、用 $x-\sigma y$ 替换 $x$，会保持这组向量的整数张成；若用新向量替换池中另一条任意向量，就不能直接沿用这一结论。

## 5. 两两约化完成意味着什么

如果池中任意两个不同向量都不能通过加减缩短较长者，则称该池满足两两约化条件：

$$
\boxed{
\min\{\|x-y\|,\|x+y\|\}
\ge
\max\{\|x\|,\|y\|\},
\qquad x\ne y\in D.
}
$$

由第 2 节的恒等式，它等价于

$$
2|\langle x,y\rangle|
\le
\min\{\|x\|^2,\|y\|^2\}.
$$

设 $a=\|x\|$、$b=\|y\|$，归一化后得到

$$
|\cos\theta|
\le
\frac{\min(a,b)}{2\max(a,b)}
\le\frac12.
$$

因此，两两约化池中的不同方向满足 $60^\circ\le\theta\le120^\circ$；长度差越大，对夹角的限制越强。这个推导也说明，池中不能同时保留 $v$ 与 $-v$。

这些方向具有球面分离性，可以用球面码的容量界约束池大小；但**池容量有上界，并不等于已经控制了采样次数或运行时间**。上述约化不变量与接吻数的联系见 [Micciancio–Voulgaris，§3.2，PDF 第 8–9 页](https://cseweb.ucsd.edu/~daniele/papers/Sieve.pdf)。

还需要保留两个区别：

- 两两约化完成，只排除了当前池内的单次两向量改善；池外向量或更多向量的组合仍可能给出更短结果。
- 两两约化池已经受到夹角约束，不能直接视为独立、均匀的球面样本；第 15 篇的概率模型需要在指定分析阶段使用。

这一不变量是 GaussSieve 类结构的重要特征，不应默认所有筛法都完整维护它。

## 6. 基本成本与计数对象

若每条向量保存 $s$ 个坐标，并缓存平方范数，则在通常的算术操作计数下：

- 检查一个向量对需要 $O(s)$ 次运算。
- 对大小为 $N$ 的池完成一次线性扫描需要 $O(sN)$ 次运算。
- 完成一次全对扫描需要 $O(sN^2)$ 次运算。
- 保存向量坐标需要 $O(sN)$ 个数；位复杂度还取决于坐标表示长度。

第 15 篇在等长、独立均匀方向模型下解释了常见的基准规模：

$$
N=2^{0.2075\ldots s+o(s)},
\qquad
N^2=2^{0.4150\ldots s+o(s)}.
$$

第一个指数来自为单个目标提供约化伙伴的概率尺度，第二个来自全对检查。它们不能单独证明完整算法的成功率和总运行时间；总成本还包括采样、反复扫描、更新、轮数及访存。

后续分析分桶筛法时，应分别记录：

1. **向量对检查次数**：同一对被检查多次，每次都产生成本。
2. **去重后的可约化源向量对数**：用于描述找到了多少不同的有效配对。
3. **去重后的非零结果数与实际池更新数**：不同源向量对可能得到相同结果，候选也可能未被接纳。

这里的“去重”表示对象不同，不表示相关事件在概率意义上独立。寻找一个有效向量对、产生一个新向量和推动向量池改善，是三个需要分别计量的事件。

## 7. 停止条件与正确性

常见停止条件有不同含义。

**达到目标长度。** 找到 $0\ne v\in\Lambda$ 且 $\|v\|\le r$，就完成了指定长度目标。除非另有最短性证明，否则不能仅凭达到某个高斯启发式比例就声称解出了精确 SVP。

**达到启发式停止条件。** 碰撞次数达到阈值、改善停滞或计算预算耗尽，可以作为运行控制条件；停止本身不证明不存在更短向量。

**达到指定饱和度。** 先规定目标半径，再检查池中该半径内的不同短向量是否足够多。例如，每个符号对 $\{\pm v\}$ 只存一条代表时，记

$$
M_D(\alpha)
=
\#\{v\in D:\|v\|\le\alpha\operatorname{gh}(\Lambda)\},
\qquad \alpha>1.
$$

由第 15 篇的高斯启发式，可用

$$
\boxed{
M_D(\alpha)\ge \kappa\,\frac{\alpha^s}{2},
\qquad 0<\kappa<1,
}
$$

作为一种启发式计数条件。这里 $\kappa$ 是设定的目标比例，分母 $2$ 来自符号对计数；如果同时存储正负向量，计数约定也应相应改变。这不是对目标球内真实格点总数的精确覆盖认证。

G6K 按预期短向量数量的一定比例设置停止条件，见 [G6K，EUROCRYPT 2019，§5.1，PDF 第 17 页](https://ir.cwi.nl/pub/28539/2019-089.pdf)。本节公式使用第 15 篇的 $\operatorname{gh}$ 定义及单个符号代表约定写出。

**两两约化完成描述池内几何关系，饱和度描述目标长度范围内的向量数量；二者不能相互替代。**

可证明算法还需要控制采样分布、碰撞概率和失败概率。原始 ListSieve 的保证依赖这些设计；Micciancio–Voulgaris 原文对实用 GaussSieve 给出了空间控制，但没有给出对应的最坏情况时间界。不能把前者的保证直接移给省略扰动后的算法。参见 [原文 §3.1，Theorem 3.1，以及 §3.2，PDF 第 6–9 页](https://cseweb.ucsd.edu/~daniele/papers/Sieve.pdf)。

后续可用这一框架比较 Nguyen–Vidick、ListSieve 与 GaussSieve：分别核对采样方式、约化对象、更新不变量、停止条件，以及结论依赖的是证明、启发式还是实验。

## 引用此笔记

- [00 概览与阅读路线](/knowledge/lattices-overview/)
- [18 Nguyen–Vidick、ListSieve 与 GaussSieve](/knowledge/nguyen-vidick-listsieve-and-gausssieve/)
- [19 筛法中的近邻搜索与分桶](/knowledge/nearest-neighbor-search-and-bucketing/)
- [25 渐进筛法与向量池复用](/knowledge/progressive-sieving-and-vector-pool-reuse/)
- [26 G6K 与 Pump](/knowledge/g6k-and-pump/)