整理日期：2026-10-17。
适用范围：逐步增加筛法维数时的向量池复用、长度与方向变化，以及补样、再筛和成本分析。
前置笔记：15 高斯启发式与随机球面模型、16 投影格、BKZ 与局部 SVP、17 筛法的基本框架与两向量约化。

固定满秩列基 $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 页中，将低维筛出的短向量池用于后续加维；其中的渐进子过程沿基的前缀扩展。下面使用局部投影格统一说明向右与向左两种操作。

2. 向右扩展：旧向量仍在原来的子空间中
#

当 $j<n$ 时，把窗口从 $[i,j]$ 扩展为 $[i,j+1]$。对旧向量

x=\sum_{k=i}^{j}z_k\pi_i(b_k),

只需在整数系数末尾补零：

(z_i,\ldots,z_j) \longmapsto (z_i,\ldots,z_j,0).

实际向量没有改变，因此

\|x_{\mathrm R}\|=\|x\|, \qquad \langle x_{\mathrm R},y_{\mathrm R}\rangle=\langle x,y\rangle.

旧向量之间的长度、夹角和两两约化关系保持不变，但它们在新增 GSO 方向 $b_{j+1}^*$ 上的分量全为零。

第 17 篇的整数张成性质给出一个直接结论：只对这些旧向量反复加减，所有结果仍留在旧池生成的子格中。 要探索新增方向，必须引入该方向分量非零的向量。

因此，向右扩展保留了已有的短向量，却没有自动获得新空间中的方向覆盖。

3. 向左扩展：补入一个 Babai 残差
#

当 $i>1$ 时，把窗口从 $[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 页；原文采用从 $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}$。一般有

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 页记录了向右扩展的一个实现问题：较长的新样本可能被旧池的短向量组合替换，导致新增方向缺乏代表。该观察针对文中的实现与替换规则，不构成向右扩展普遍失效的结论。

5. 扩展、补样与再筛的基本流程
#

下面给出固定右端点、逐步向左扩展的简化流程。设目标窗口为 $[a,j]$，初始左端点满足 $a\le i_0\le j$：

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 页。

每次加维后，应分别检查：

合法性与覆盖范围： 向量属于当前格；采样与更新能探索所需方向。满秩本身也不代表方向近似均匀。
长度与数量： 使用当前窗口的参考长度和目标规模。总数量达标不等于短向量数量达标。
停止条件： 沿用第 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 重复配对、去重与有效覆盖分别统计。

7. 与后续格约化策略的衔接
#

本篇先固定基，只讨论加维与复用。完整格约化还会插入短向量、改变基、缩小或移动窗口；这时需要同步处理整数系数和投影空间的变化，不能只修改窗口下标。

后续的 G6K/Pump 笔记将进一步组织这些操作，并结合第 16 篇的 dimensions for free，区分筛法范围、提升范围和插入位置。

对于渐进加维后的概率建模，值得保留三个观察对象：归一化长度分布、新增方向的分量分布，以及新旧向量之间的夹角与约化概率。 它们连接本篇的确定性几何关系与后续的模型修正、选参和实验研究。

引用此笔记
#

26 G6K 与 Pump

1. 从低维向量池逐步扩展#

2. 向右扩展：旧向量仍在原来的子空间中#

3. 向左扩展：补入一个 Babai 残差#

4. 长度尺度与目标池规模也要更新#

$$ \frac{|x_{\mathrm{new}}|/h_{\mathrm{new}}} {|x|/h_{\mathrm{old}}}#

5. 扩展、补样与再筛的基本流程#

6. 渐进运行的成本#

$$ T_{\mathrm{prog}}#

7. 与后续格约化策略的衔接#

引用此笔记#