↓ 跳过正文
ShiJin

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

Markdown 版本

目录

整理日期：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)}. \]

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

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

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

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

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

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

引用此笔记
#