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

整理日期：2026-10-16。
适用范围：欧氏格上的两向量筛法、向量池维护，以及局部约化、运行成本和停止条件的区别。
前置笔记：15 高斯启发式与随机球面模型、16 投影格、BKZ 与局部 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 页。

以下先讨论直接处理格向量的基本操作；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$ 。下面是根据上一节判据写出的基础子程序：

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 页。本节伪代码省略了原始 ListSieve 的扰动与缩短因子，只表示直接格向量上的基本操作。

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

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

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

两种典型组织方式是：

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

批量结构可对照 Nguyen–Vidick，2008，作者稿 §4.1，Algorithms 4–5，PDF 第 13–14 页；增量结构与旧向量回收可对照 Micciancio–Voulgaris，SODA 2010，作者稿 19 页版，§3.2，Algorithm 2，PDF 第 8–9 页。

两类结构都利用向量相减，但并非每一步都调用上一节的 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 页。

还需要保留两个区别：

两两约化完成，只排除了当前池内的单次两向量改善；池外向量或更多向量的组合仍可能给出更短结果。
两两约化池已经受到夹角约束，不能直接视为独立、均匀的球面样本；第 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)}.

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

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

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

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

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 页。本节公式使用第 15 篇的 $\operatorname{gh}$ 定义及单个符号代表约定写出。

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

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

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

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

#1. 筛法维护什么

#2. 两向量约化的判据

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

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

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

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

#7. 停止条件与正确性

#引用此笔记