# 25 渐进筛法与向量池复用 整理日期：2026-10-17。 适用范围：逐步增加筛法维数时的向量池复用、长度与方向变化，以及补样、再筛和成本分析。 前置笔记：[15 高斯启发式与随机球面模型](/knowledge/gaussian-heuristic-and-random-spheres/)、[16 投影格、BKZ 与局部 SVP](/knowledge/projected-lattices-bkz-and-local-svp/)、[17 筛法的基本框架与两向量约化](/knowledge/lattice-sieving-basics/)。 固定满秩列基 $B=(b_1,\ldots,b_n)$，沿用第 16 篇的投影记号： $$ \Lambda_{[i,j]} =\mathcal L\bigl(\pi_i(b_i),\ldots,\pi_i(b_j)\bigr), \qquad s=j-i+1,\qquad g_k=\|b_k^*\|. $$ 下标从 $1$ 开始，区间包含两端。以下加维操作均针对同一组固定基 $B$；$s$ 表示当前筛法维数，向量池 $D$ 只保留非零向量。 ## 1. 从低维向量池逐步扩展 渐进筛法先在较小的局部格中筛出一批短向量，再扩大窗口，保留已有结果，继续补样和约化。 复用的对象是整个向量池：旧向量既是后续搜索的候选，也是缩短新样本的约化伙伴。窗口和向量表示随之更新，旧池的停止状态则需要在新空间中重新检查。 Ducas 在 [《Shortest Vector from Lattice Sieving: A Few Dimensions for Free》§4.3，PDF 第 12 页](https://ir.cwi.nl/pub/27649/27649.pdf)中，将低维筛出的短向量池用于后续加维；其中的渐进子过程沿基的前缀扩展。下面使用局部投影格统一说明向右与向左两种操作。 ## 2. 向右扩展：旧向量仍在原来的子空间中 当 $j1$ 时，把窗口从 $[i,j]$ 扩展为 $[i-1,j]$。沿用第 16 篇的 GSO 系数 $\mu_{k,i-1}$，令 $$ c_x=\sum_{k=i}^{j}\mu_{k,i-1}z_k, \qquad q_x=\operatorname{round}(c_x), \qquad \varepsilon_x=c_x-q_x. $$ 新的整数系数为 $$ (z_i,\ldots,z_j) \longmapsto (-q_x,z_i,\ldots,z_j). $$ 对应向量满足 $$ \boxed{ x_{\mathrm L}=x+\varepsilon_x b_{i-1}^*, \qquad \pi_i(x_{\mathrm L})=x, \qquad |\varepsilon_x|\le\tfrac12. } $$ 这是第 16 篇 Babai 提升的一步形式。两种窗口操作可对照 [G6K，EUROCRYPT 2019，§3.2，PDF 第 9 页](https://ir.cwi.nl/pub/28539/2019-089.pdf)；原文采用从 $0$ 开始、右端点不包含在内的区间，需换算下标。 由正交性直接得到 $$ \boxed{ \|x_{\mathrm L}\|^2 =\|x\|^2+\varepsilon_x^2g_{i-1}^2 \le \|x\|^2+\frac14g_{i-1}^2. } $$ 对两条旧向量，还有 $$ \langle x_{\mathrm L},y_{\mathrm L}\rangle =\langle x,y\rangle +\varepsilon_x\varepsilon_y g_{i-1}^2, $$ 以及对 $\sigma\in\{-1,1\}$， $$ \boxed{ \|x_{\mathrm L}-\sigma y_{\mathrm L}\|^2 =\|x-\sigma y\|^2 +(\varepsilon_x-\sigma\varepsilon_y)^2g_{i-1}^2. } $$ 这些关系说明：向左提升可能改变长度和内积，旧池的两两约化状态未必保留，原来的最佳加减符号也可能改变。新的约化条件应使用提升后的真实几何量。 $\varepsilon_x$ 由整数系数和当前基确定。在额外的连续均匀残差模型 $\varepsilon_x\sim\operatorname{Unif}[-1/2,1/2]$ 中，平均平方长度增量为 $g_{i-1}^2/12$。取整操作本身不保证这种均匀性，也不保证不同向量的残差相互独立。 ## 4. 长度尺度与目标池规模也要更新 沿用第 15–16 篇的高斯启发式定义，记 $$ h_{i,j} =\operatorname{gh}(\Lambda_{[i,j]}) =\left(\frac{\prod_{k=i}^{j}g_k}{V_s}\right)^{1/s}, $$ 其中 $V_s$ 是 $s$ 维单位球体积。令 $\Delta_{i,j}=\prod_{k=i}^{j}g_k$，则加维后 $$ h_{i,j+1} =\left(\frac{\Delta_{i,j}g_{j+1}}{V_{s+1}}\right)^{1/(s+1)}, \qquad h_{i-1,j} =\left(\frac{g_{i-1}\Delta_{i,j}}{V_{s+1}}\right)^{1/(s+1)}. $$ 比较不同窗口中的“短”，应同时记录绝对长度与归一化长度 $\|x\|/h_{i,j}$。一般有 $$ \frac{\|x_{\mathrm{new}}\|/h_{\mathrm{new}}} {\|x\|/h_{\mathrm{old}}} = \frac{\|x_{\mathrm{new}}\|}{\|x\|} \frac{h_{\mathrm{old}}}{h_{\mathrm{new}}}. $$ 所以，向右扩展虽然不改变绝对长度，归一化长度仍可能变化；向左提升的绝对长度不减，也不能单凭这一点判断相对质量。 池规模同样依赖维数。以第 15 篇的两向量筛法规模为参照，若采用简化目标 $$ N_{\mathrm{tar}}(s) =\left\lceil c_N(4/3)^{s/2}\right\rceil, \qquad c_N>0\ \text{固定}, $$ 忽略取整，并假设旧池恰有 $N_{\mathrm{tar}}(s)$ 条向量，全部保留后只补足下一维的目标数量，则新样本约占扩容后池的 $$ 1-\frac{N_{\mathrm{tar}}(s)}{N_{\mathrm{tar}}(s+1)} \approx 1-\frac{\sqrt3}{2} \approx 13.4\%. $$ 这只是该容量规则下的数量比例，不能用来保证方向覆盖或混合充分。 G6K 的 [§4.5，PDF 第 16 页](https://ir.cwi.nl/pub/28539/2019-089.pdf)记录了向右扩展的一个实现问题：较长的新样本可能被旧池的短向量组合替换，导致新增方向缺乏代表。该观察针对文中的实现与替换规则，不构成向右扩展普遍失效的结论。 ## 5. 扩展、补样与再筛的基本流程 下面给出固定右端点、逐步向左扩展的简化流程。设目标窗口为 $[a,j]$，初始左端点满足 $a\le i_0\le j$： ~~~text ProgressiveLeft(B, a, i₀, j): i ← i₀ D ← 在 Λ_[i,j] 中初始化并筛至当前阶段的停止条件 当 i > a： D ← 对每条向量做一步 Babai 向左提升 i ← i − 1 更新当前窗口的维数、参考长度与目标池规模 更新向量表示及依赖当前空间的缓存和搜索索引 D ← 按当前采样策略补充新样本 D ← 继续约化、去重和更新，直到满足本阶段停止条件 返回 D ~~~ 这是组织流程的伪代码；具体筛法、采样器和停止规则需要另外指定。G6K 用可组合的窗口操作与筛法调用表达这类过程，参见 [§3.3–§4.1，PDF 第 11–12 页](https://ir.cwi.nl/pub/28539/2019-089.pdf)。 每次加维后，应分别检查： - **合法性与覆盖范围：** 向量属于当前格；采样与更新能探索所需方向。满秩本身也不代表方向近似均匀。 - **长度与数量：** 使用当前窗口的参考长度和目标规模。总数量达标不等于短向量数量达标。 - **停止条件：** 沿用第 17 篇的区别，分别判断长度目标、两两约化状态和启发式饱和度；不能直接继承上一维的停止结论。 再筛可以继续改善向量池，但不能仅由“已经再筛”推出其成为独立均匀的球面样本。 ## 6. 渐进运行的成本 逐维运行的总时间可以分解为 $$ T_{\mathrm{prog}} = \sum_{s=s_0}^{d} \bigl( T_{\mathrm{transfer},s} +T_{\mathrm{sample},s} +T_{\mathrm{index},s} +T_{\mathrm{resieve},s} \bigr), $$ 分别计入初始化或池迁移、补样、索引维护和继续筛法。这里 $d$ 是本次运行的最大筛法维数；继续筛法的成本还取决于传入池的状态。 为理解低维阶段的开销，假设从头运行一次 $s$ 维筛法的成本近似为 $A c_T^s$，其中 $A>0$、$c_T>1$ 固定。几何级数给出 $$ \sum_{s=s_0}^{d}A c_T^s \le \frac{A c_T^d}{1-c_T^{-1}}. $$ 在这个简化模型下，逐维完整计算的总成本是末维成本的常数倍。这个式子只说明前面各维的开销尺度；**复用是否加速，取决于它节省的后续筛法工作能否抵消迁移、补样与维护开销。** 实验比较应固定输入基和最终长度质量或饱和目标，比较从头运行与渐进复用的总时间、峰值内存及阶段成本。检查次数、不同有效源对、不同结果和实际接纳数量，沿用[24 重复配对、去重与有效覆盖](/knowledge/duplicate-pairs-and-effective-coverage/)分别统计。 ## 7. 与后续格约化策略的衔接 本篇先固定基，只讨论加维与复用。完整格约化还会插入短向量、改变基、缩小或移动窗口；这时需要同步处理整数系数和投影空间的变化，不能只修改窗口下标。 后续的 G6K/Pump 笔记将进一步组织这些操作，并结合第 16 篇的 dimensions for free，区分筛法范围、提升范围和插入位置。 对于渐进加维后的概率建模，值得保留三个观察对象：**归一化长度分布、新增方向的分量分布，以及新旧向量之间的夹角与约化概率。** 它们连接本篇的确定性几何关系与后续的模型修正、选参和实验研究。 ## 引用此笔记 - [26 G6K 与 Pump](/knowledge/g6k-and-pump/)