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

设当前处理的格为 $\Lambda=\mathcal L(C)$ ，秩为 $s$ ，使用欧氏范数。在 BKZ 中， $\Lambda$ 可以是投影格、BKZ 与局部 SVP的局部投影格；这里的 $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)}$ 乘输入长度多项式的时间界 [1, pp. 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$ ，条件退化为高斯启发式与随机球面模型的

|\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$ 后，它可能又能被此前检查过的其他向量缩短。

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

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

列表约化可以引入缩短因子，将每次更新要求的长度下降与迭代次数控制联系起来 [2, pp. 3–4]。本节伪代码省略了原始 ListSieve 的扰动与缩短因子，只表示直接格向量上的基本操作。

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

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

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

两种典型组织方式是：

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

Nguyen–Vidick 算法采用按轮处理向量列表的批量结构 [3, pp. 13–14]。GaussSieve 采用逐个约化、更新数据库并回收旧向量的增量结构 [4, pp. 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$ 。

这些方向具有球面分离性，可以用球面码的容量界约束池大小 [4, pp. 8–9]。但池容量有上界，并不等于已经控制了采样次数或运行时间。

还需要保留两个区别：

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

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

6. 基本成本与计数对象

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

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

高斯启发式与随机球面模型在等长、独立均匀方向模型下解释了常见的基准规模：

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.

由高斯启发式与随机球面模型的高斯启发式，可用

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

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

G6K 按预期短向量数量的一定比例设置停止条件 [5, p. 17]。本节公式使用高斯启发式与随机球面模型的 $\operatorname{gh}$ 定义及单个符号代表约定写出。

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

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

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

参考文献

1. Oded Regev. Lecture 8: $`2^{O(n)}`$ -time algorithm for SVP. 2004. 原文.

2. Daniele Micciancio. Sieving algorithms for exact SVP. 2021. 原文.

3. Phong Q. Nguyen and Thomas Vidick. Sieve algorithms for the shortest vector problem are practical. Journal of Mathematical Cryptology. 2008. DOI.

4. Daniele Micciancio and Panagiotis Voulgaris. Faster exponential time algorithms for the shortest vector problem. Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms. 2010. DOI.

5. Martin R. Albrecht, Léo Ducas, Gottfried Herold, Elena Kirshanova, Eamonn W. Postlethwaite, and Marc Stevens. The general sieve kernel and new records in lattice reduction. Advances in cryptology – EUROCRYPT 2019. 2019. DOI.

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

#1. 筛法维护什么

#2. 两向量约化的判据

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

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

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

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

#7. 停止条件与正确性

#参考文献