整理日期：2026-10-16。
适用范围：三种经典欧氏格筛法的采样、约化、更新与停止机制，以及各自的理论保证。
前置笔记：15 高斯启发式与随机球面模型、17 筛法的基本框架与两向量约化。局部投影环境见第 16 篇。
设当前格为 \(\Lambda=\mathcal L(B)\)，实际筛法维数为 \(s\ge2\)。沿用列基和欧氏范数；复杂度表述略去输入位长等多项式因子。
本文的 NV 指 Nguyen–Vidick 2008 的启发式批量筛法，ListSieve 指 Micciancio–Voulgaris 的原始带扰动算法，GaussSieve 指其直接处理格向量的实用变体。
下面的伪代码用于突出核心机制，显式处理零向量和结果记录。NV 与 ListSieve 保留原文的相减形式；GaussSieve 显式检查加减两种符号。
1. Nguyen–Vidick：按轮缩短，消耗中心#
NV 先生成 \(N\) 条初始格向量，再反复调用一次筛选操作。原文以 LLL 预处理后的基为输入，采用 Klein 型随机化最近平面采样；初始采样的性质不能自动保证后续各轮仍满足所需分布假设。
给定非空列表 \(S\)，令
本轮构造中心列表 \(H\) 和输出列表 \(S'\)：
NVStep(S, γ):
R ← S 中的最大长度
H ← 空列表
S′ ← 空列表
对每个 v ∈ S：
如果 ||v|| ≤ γR：
w ← v
否则，如果存在 c ∈ H 满足 ||v−c|| ≤ γR：
w ← v−c
否则：
将 v 加入 H
继续处理下一个向量
如果 w ≠ 0：
将 w 加入 S′
返回 S′每轮中心只用于处理本轮后续向量，不进入下一轮。原始外层流程重复筛选直到列表为空，返回最后一个非空列表中的最短向量；实现时也可以持续记录遇到的最短非零向量。算法与采样入口见 Nguyen–Vidick，2008，作者稿 28 页版，§4.1，Algorithms 4–5，以及 §4.2.1，PDF 第 13–17 页。
由伪代码直接得到：只要下一轮非空，
但较小的半径不保证仍有足够多的向量。中心不进入输出、归零以及去重都会减少可用样本；若过早耗尽，返回值未必接近最短向量。这里允许列表保留重复项；若额外去重，需要将其损耗计入模型。
原文的启发式假设是：每轮参与筛选的长向量近似均匀分布于球壳
其球壳覆盖分析使用指数因子
在相应启发式及参数设置下，样本规模和时间的指数基准分别为 \(c_\gamma^s\) 与 \(c_\gamma^{2s}\)，另含多项式因子。当 \(\gamma\to1\) 时，
这解释了常见的两个指数；固定 \(\gamma<1\) 时不能直接把它们当作精确值。更接近 \(1\) 的 \(\gamma\) 也意味着每轮缩短更少、所需轮数更多。来源见 原文 §4.1，Heuristic、Lemma 4.1 及复杂度讨论，PDF 第 14–16 页。
因此，应分别记录：半径收缩是算法保证，分布保持与预期输出质量依赖启发式；不能把 NV 论文中对 AKS 的证明直接用于这个简化版本。
2. ListSieve：约化带扰动的点，保留已有列表#
ListSieve 的输入除了格基，还包括目标长度 \(\mu>0\)。目标是找到
它维护只增不改的格向量列表 \(D\)。关键区别在于：约化判断作用于一个带扰动的点 \(p\)，而非直接作用于待输出的格向量。
取扰动参数 \(\xi>1/2\)，采样
其中 \(\mathcal P(B)=\{Bt:t\in[0,1)^s\}\)，取模表示选择同一格陪集在基本区域中的代表。于是
固定这次采样的 \(e\)，反复从 \(p\) 中减去列表中的格向量。每次更新都保持 \(p-e\in\Lambda\)，最后恢复 \(v=p-e\)。中间点 \(p\) 一般不属于格，列表中的向量始终属于格。
取长度缩短因子 \(\delta=1-1/s\)；这里的 \(\delta\) 只表示本子程序的缩短比例。
ListSieve(B, μ, ξ, δ, K):
D ← {0} # 0 用于统一检查候选自身的长度
重复 K 次：
e ← 在半径 ξμ 的球内均匀采样
p ← e mod P(B)
当存在 u ∈ D \ {0} 满足 ||p−u|| ≤ δ||p||：
p ← p−u
v ← p−e
如果 v ∈ D：
继续下一次采样
如果存在 u ∈ D 满足 0 < ||v−u|| ≤ μ：
返回 v−u
将 v 加入 D # 已有向量不修改、不移除
返回 ⊥ # 本次未找到目标向量这里显式排除了零约化向量，并按非零、长度至多 \(\mu\) 的目标写出返回检查；核心结构对应 Micciancio–Voulgaris，SODA 2010，作者稿 19 页版，§3.1，Algorithm 1，PDF 第 6–7 页。
扰动保留了分析碰撞概率所需的随机性：给定采样阶段的初始 \(p\)，\(p-e\) 在 \(\Lambda\cap B_s(p,\xi\mu)\) 上均匀分布。约化选择只依赖 \(p\) 和当前列表，恢复格向量时才使用 \(e\)；这使证明能够比较“得到重复向量”和“得到新的短差向量”的概率。相关解释见 Micciancio《Sieving Algorithms for Exact SVP》，正文标注 Fall 2021，§2.2.1 与 §2.3.2。
其证明可以按两部分理解：
- 控制列表容量。 尚未返回目标解时，列表中不同向量的距离大于 \(\mu\)；再结合约化产生的几何约束，得到列表大小上界。
- 控制无效采样。 扰动与碰撞概率分析保证：采样次数足够多时，不能一直重复而不找到目标解。
当 \(\lambda_1(\Lambda)\le\mu\)，按定理选择采样预算 \(K\)，并取 \(\xi\approx0.685\)，原文给出高概率成功及以下复杂度界：
这是原始带扰动 ListSieve 的可证明界。来源见 原文 Theorem 3.1、Corollary 3.2 及 Appendix A。
返回向量可以直接验证；返回 \(\perp\) 则可能是随机失败，不能视为不存在短向量的确定证书。配合外层长度搜索和失败概率控制，才能将该目标长度子程序用于精确 SVP。
此外，停止约化的是 \(p\)。恢复后的 \(v=p-e\) 不自动满足第 17 篇的两两约化条件，已有列表也不会被 \(v\) 反向约化。
3. GaussSieve：双向约化与待处理队列#
GaussSieve 直接采样格向量，使用两个容器：
- \(D\)：已经维护好两两约化关系的非零向量列表。
- \(Q\)：因更新而需要重新处理的向量队列或栈。
每次优先从 \(Q\) 取向量；只有 \(Q\) 为空时才生成新样本。处理候选 \(v\) 分为两步：
- 用 \(D\) 中不长于 \(v\) 的向量反复缩短 \(v\)。
- 用处理后的 \(v\) 缩短列表中更长的向量，将这些旧向量移出，约化结果放入 \(Q\)。
令 \(\operatorname{Shorter}(a\pm b)\) 表示从 \(a-b,a+b\) 中选择较短者。下面采用严格变短条件，并记录遇到的最短非零向量：
GaussSieve(B, c_max):
D ← 空列表
Q ← 空队列
collisions ← 0
best ← B 中最短的基向量
当 collisions < c_max：
v ← 从 Q 取出一个向量；若 Q 为空，则采样格向量
当 v ≠ 0 且存在 u ∈ D 满足
||u|| ≤ ||v|| 且 min(||v−u||, ||v+u||) < ||v||：
v ← Shorter(v±u)
# v 改变后，重新扫描 D
如果 v = 0：
collisions ← collisions + 1
继续下一轮
用 v 更新 best
对 D 中每个满足以下条件的 u：
||u|| > ||v|| 且 min(||u−v||, ||u+v||) < ||u||：
从 D 移除 u
w ← Shorter(u±v)
将 w 放入 Q
用 w 更新 best
将 v 加入 D
返回 best这个整理版显式写出了符号选择、严格变短和结果记录。原始机制见 Micciancio–Voulgaris，§3.2，Algorithm 2，PDF 第 8–9 页。
为什么旧向量需要进入队列，可以直接由第 17 篇理解：旧向量一旦改变，就可能再次被其他列表向量缩短，不能直接留在已处理列表中。
插入 \(v\) 后，\(D\) 仍满足两两约化条件：不长于 \(v\) 的旧向量已经与它检查过；更长且可被它缩短的旧向量已被移出。这个不变量属于 \(D\)，不要求待处理的 \(Q\) 同时满足。
由第 17 篇的夹角推导，\(D\) 的归一化方向之间至少相隔 \(60^\circ\)，因此可用 \(s\) 维接吻数 \(\tau_s\) 控制列表容量，例如 \(|D|\le\tau_s\)。这里 \(\tau_s\) 表示单位球面上最小夹角至少为 \(60^\circ\) 的点集的最大大小。
队列只回收已有向量，且队列未清空时不增加新样本，因此总存储也能按同一数量级控制。不过，容量界并没有控制需要多少次新采样。此处的空间论证与时间分析之间的区别，见 Micciancio 讲义 §3.1，PDF 第 13–15 页。
伪代码中的 \(c_{\max}\) 是累计归零次数阈值，不是连续碰撞次数。它是启发式停止条件；队列清空、碰撞增多或列表两两约化，都不能单独证明已经找到最短向量。
若额外采用经典的池规模与处理次数启发式，常用估计为
这类估计可作为算法比较的基线，不能由接吻数上界直接推出，也不能当成原始论文已证明的最坏情况时间界。参见 Micciancio 讲义 §3.1–§3.2，Table 1，PDF 第 15–16 页。
4. 阅读三种算法时怎样对应#
三者最值得保留的区别是：
- NV：按轮缩小半径。 中心在本轮使用后丢弃，分析同时追踪半径收缩与样本损耗。
- ListSieve：带扰动地增加列表。 旧向量不变，以列表容量和碰撞概率分析得到高概率时间保证。
- GaussSieve：维护两两约化关系。 新旧向量相互约化，队列负责重新处理；几何不变量更直接，但原始 ListSieve 的概率证明不能原样搬过来。
碰撞的含义也随流程变化：NV 中可以表现为相同样本相减归零；ListSieve 显式检查恢复出的向量是否已在列表中；GaussSieve 通过候选最终归零计数。比较运行记录时，应先核对统计口径。
还要区分原始 NV 与后续实现变体。例如，G6K 的 nv 实现使用固定大小数据库；发现足够短的 \(x\pm y\) 后，替换数据库中最长的向量。它不要求被替换者就是 \(x\) 或 \(y\)，也不是上面按轮消耗中心的伪代码。G6K 明确将其称为 NV 的放松版本，见 G6K，EUROCRYPT 2019，§4.5–§5.1，PDF 第 16–17 页。
这种变化会影响整数张成与秩的保持，相关代数区别已经在第 17 篇说明。阅读 BGJ 或具体实现时，需要先确定它沿用哪一种数据库更新规则。
5. 与近邻搜索和分桶的衔接#
以上基础版本中，昂贵操作都包含：给定一个候选，在已有向量中寻找满足长度条件的伙伴。
后续近邻搜索与分桶主要改变这个搜索过程：先缩小候选范围，再验证真实的约化条件。研究这种改进时，需要同时保留：
- 搜索能覆盖多少有效向量对；
- 同一向量对会被重复检查多少次；
- 搜索结果如何进入原有的列表、队列或固定数据库；
- 加速后是否仍维护所需的不变量。
下一篇《19 筛法中的近邻搜索与分桶》从线性扫描进入近邻问题，再逐步讨论 LSH、LSF 以及筛法中的分桶机制。