渐进筛法与向量池复用 前置笔记：高斯启发式与随机球面模型 、投影格、BKZ 与局部 SVP 、筛法的基本框架与两向量约化 。
固定满秩列基 B = ( b 1 , … , b n ) B=(b_1,\ldots,b_n) B = ( b 1 , … , b n ) 投影格、BKZ 与局部 SVP 的投影记号：
Λ [ i , j ] = L ( π i ( b i ) , … , π i ( b j ) ) , s = j − i + 1 , g k = ∥ b k ∗ ∥ . \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^*\|. Λ [ i , j ] = L ( π i ( b i ) , … , π i ( b j ) ) , s = j − i + 1 , g k = ∥ b k ∗ ∥. 下标从 1 1 1 B B B s s s D D D
1. 从低维向量池逐步扩展
渐进筛法先在较小的局部格中筛出一批短向量，再扩大窗口，保留已有结果，继续补样和约化。
复用的对象是整个向量池：旧向量既是后续搜索的候选，也是缩短新样本的约化伙伴。窗口和向量表示随之更新，旧池的停止状态则需要在新空间中重新检查。
Ducas 将低维筛出的短向量池用于后续加维；其中的渐进子过程沿基的前缀扩展 [1, p. 12 ]。下面使用局部投影格统一说明向右与向左两种操作。
2. 向右扩展：旧向量仍在原来的子空间中
当 j < n j<n j < n [ i , j ] [i,j] [ i , j ] [ i , j + 1 ] [i,j+1] [ i , j + 1 ]
x = ∑ k = i j z k π i ( b k ) , x=\sum_{k=i}^{j}z_k\pi_i(b_k), x = k = i ∑ j z k π i ( b k ) , 只需在整数系数末尾补零：
( z i , … , z j ) ⟼ ( z i , … , z j , 0 ) . (z_i,\ldots,z_j)
\longmapsto
(z_i,\ldots,z_j,0). ( z i , … , z j ) ⟼ ( z i , … , z j , 0 ) . 实际向量没有改变，因此
∥ x R ∥ = ∥ x ∥ , ⟨ x R , y R ⟩ = ⟨ x , y ⟩ . \|x_{\mathrm R}\|=\|x\|,
\qquad
\langle x_{\mathrm R},y_{\mathrm R}\rangle=\langle x,y\rangle. ∥ x R ∥ = ∥ x ∥ , ⟨ x R , y R ⟩ = ⟨ x , y ⟩ . 旧向量之间的长度、夹角和两两约化关系保持不变，但它们在新增 GSO 方向 b j + 1 ∗ b_{j+1}^* b j + 1 ∗
筛法基本框架 的整数张成性质给出一个直接结论：只对这些旧向量反复加减，所有结果仍留在旧池生成的子格中。 要探索新增方向，必须引入该方向分量非零的向量。
因此，向右扩展保留了已有的短向量，却没有自动获得新空间中的方向覆盖。
3. 向左扩展：补入一个 Babai 残差
当 i > 1 i>1 i > 1 [ i , j ] [i,j] [ i , j ] [ i − 1 , j ] [i-1,j] [ i − 1 , j ] 投影格、BKZ 与局部 SVP 的 GSO 系数 μ k , i − 1 \mu_{k,i-1} μ k , i − 1
c x = ∑ k = i j μ k , i − 1 z k , q x = round ( c x ) , ε x = c x − q x . 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. c x = k = i ∑ j μ k , i − 1 z k , q x = round ( c x ) , ε x = c x − q x . 新的整数系数为
( z i , … , z j ) ⟼ ( − q x , z i , … , z j ) . (z_i,\ldots,z_j)
\longmapsto
(-q_x,z_i,\ldots,z_j). ( z i , … , z j ) ⟼ ( − q x , z i , … , z j ) . 对应向量满足
x L = x + ε x b i − 1 ∗ , π i ( x L ) = x , ∣ ε x ∣ ≤ 1 2 . \boxed{
x_{\mathrm L}=x+\varepsilon_x b_{i-1}^*,
\qquad
\pi_i(x_{\mathrm L})=x,
\qquad
|\varepsilon_x|\le\tfrac12.
} x L = x + ε x b i − 1 ∗ , π i ( x L ) = x , ∣ ε x ∣ ≤ 2 1 . 这是投影格、BKZ 与局部 SVP Babai 提升的一步形式。G6K 论文中的两种窗口操作采用从 0 0 0 2, p. 9 ]。
由正交性直接得到
∥ x L ∥ 2 = ∥ x ∥ 2 + ε x 2 g i − 1 2 ≤ ∥ x ∥ 2 + 1 4 g i − 1 2 . \boxed{
\|x_{\mathrm L}\|^2
=\|x\|^2+\varepsilon_x^2g_{i-1}^2
\le \|x\|^2+\frac14g_{i-1}^2.
} ∥ x L ∥ 2 = ∥ x ∥ 2 + ε x 2 g i − 1 2 ≤ ∥ x ∥ 2 + 4 1 g i − 1 2 . 对两条旧向量，还有
⟨ x L , y L ⟩ = ⟨ x , y ⟩ + ε x ε y g i − 1 2 , \langle x_{\mathrm L},y_{\mathrm L}\rangle
=\langle x,y\rangle
+\varepsilon_x\varepsilon_y g_{i-1}^2, ⟨ x L , y L ⟩ = ⟨ x , y ⟩ + ε x ε y g i − 1 2 , 以及对 σ ∈ { − 1 , 1 } \sigma\in\{-1,1\} σ ∈ { − 1 , 1 }
∥ x L − σ y L ∥ 2 = ∥ x − σ y ∥ 2 + ( ε x − σ ε y ) 2 g i − 1 2 . \boxed{
\|x_{\mathrm L}-\sigma y_{\mathrm L}\|^2
=\|x-\sigma y\|^2
+(\varepsilon_x-\sigma\varepsilon_y)^2g_{i-1}^2.
} ∥ x L − σ y L ∥ 2 = ∥ x − σ y ∥ 2 + ( ε x − σ ε y ) 2 g i − 1 2 . 这些关系说明：向左提升可能改变长度和内积，旧池的两两约化状态未必保留，原来的最佳加减符号也可能改变。新的约化条件应使用提升后的真实几何量。
ε x \varepsilon_x ε x ε x ∼ Unif [ − 1 / 2 , 1 / 2 ] \varepsilon_x\sim\operatorname{Unif}[-1/2,1/2] ε x ∼ Unif [ − 1/2 , 1/2 ] g i − 1 2 / 12 g_{i-1}^2/12 g i − 1 2 /12
4. 长度尺度与目标池规模也要更新
沿用高斯启发式与随机球面模型 与投影格、BKZ 与局部 SVP 的高斯启发式定义，记
h i , j = gh ( Λ [ i , j ] ) = ( ∏ k = i j g k V s ) 1 / s , h_{i,j}
=\operatorname{gh}(\Lambda_{[i,j]})
=\left(\frac{\prod_{k=i}^{j}g_k}{V_s}\right)^{1/s}, h i , j = gh ( Λ [ i , j ] ) = ( V s ∏ k = i j g k ) 1/ s , 其中 V s V_s V s s s s Δ i , j = ∏ k = i j g k \Delta_{i,j}=\prod_{k=i}^{j}g_k Δ i , j = ∏ k = i j g k
h i , j + 1 = ( Δ i , j g j + 1 V s + 1 ) 1 / ( s + 1 ) , h i − 1 , j = ( g i − 1 Δ i , j V s + 1 ) 1 / ( s + 1 ) . 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)}. h i , j + 1 = ( V s + 1 Δ i , j g j + 1 ) 1/ ( s + 1 ) , h i − 1 , j = ( V s + 1 g i − 1 Δ i , j ) 1/ ( s + 1 ) . 比较不同窗口中的“短”，应同时记录绝对长度与归一化长度 ∥ x ∥ / h i , j \|x\|/h_{i,j} ∥ x ∥/ h i , j
∥ x n e w ∥ / h n e w ∥ x ∥ / h o l d = ∥ x n e w ∥ ∥ x ∥ h o l d h n e w . \frac{\|x_{\mathrm{new}}\|/h_{\mathrm{new}}}
{\|x\|/h_{\mathrm{old}}}
=
\frac{\|x_{\mathrm{new}}\|}{\|x\|}
\frac{h_{\mathrm{old}}}{h_{\mathrm{new}}}. ∥ x ∥/ h old ∥ x new ∥/ h new = ∥ x ∥ ∥ x new ∥ h new h old . 所以，向右扩展虽然不改变绝对长度，归一化长度仍可能变化；向左提升的绝对长度不减，也不能单凭这一点判断相对质量。
池规模同样依赖维数。以高斯启发式与随机球面模型 的两向量筛法规模为参照，若采用以下简化目标，并保持比例常数固定：
N t a r ( s ) = ⌈ c N ( 4 / 3 ) s / 2 ⌉ , c N > 0 , N_{\mathrm{tar}}(s)
=\left\lceil c_N(4/3)^{s/2}\right\rceil,
\qquad c_N>0, N tar ( s ) = ⌈ c N ( 4/3 ) s /2 ⌉ , c N > 0 , 忽略取整，并假设旧池恰有 N t a r ( s ) N_{\mathrm{tar}}(s) N tar ( s )
1 − N t a r ( s ) N t a r ( s + 1 ) ≈ 1 − 3 2 ≈ 13.4 % . 1-\frac{N_{\mathrm{tar}}(s)}{N_{\mathrm{tar}}(s+1)}
\approx 1-\frac{\sqrt3}{2}
\approx 13.4\%. 1 − N tar ( s + 1 ) N tar ( s ) ≈ 1 − 2 3 ≈ 13.4%. 这只是该容量规则下的数量比例，不能用来保证方向覆盖或混合充分。
G6K 论文记录了向右扩展的一个实现问题：较长的新样本可能被旧池的短向量组合替换，导致新增方向缺乏代表 [2, p. 16 ]。该观察针对文中的实现与替换规则，不构成向右扩展普遍失效的结论。
5. 扩展、补样与再筛的基本流程
下面给出固定右端点、逐步向左扩展的简化流程。设目标窗口为 [ a , j ] [a,j] [ a , j ] a ≤ i 0 ≤ j a\le i_0\le j a ≤ i 0 ≤ j
ProgressiveLeft(B, a, i₀, j): i ← i₀ D ← 在 Λ_[i,j] 中初始化并筛至当前阶段的停止条件 当 i > a： D ← 对每条向量做一步 Babai 向左提升 i ← i − 1 更新当前窗口的维数、参考长度与目标池规模 更新向量表示及依赖当前空间的缓存和搜索索引 D ← 按当前采样策略补充新样本 D ← 继续约化、去重和更新，直到满足本阶段停止条件 返回 D 这是组织流程的伪代码；具体筛法、采样器和停止规则需要另外指定。G6K 用可组合的窗口操作与筛法调用表达这类过程 [2, pp. 11–12 ]。
每次加维后，应分别检查：
合法性与覆盖范围： 向量属于当前格；采样与更新能探索所需方向。满秩本身也不代表方向近似均匀。长度与数量： 使用当前窗口的参考长度和目标规模。总数量达标不等于短向量数量达标。停止条件： 沿用筛法基本框架 的区别，分别判断长度目标、两两约化状态和启发式饱和度；不能直接继承上一维的停止结论。
再筛可以继续改善向量池，但不能仅由“已经再筛”推出其成为独立均匀的球面样本。
6. 渐进运行的成本
逐维运行的总时间可以分解为
T p r o g = ∑ s = s 0 d ( T t r a n s f e r , s + T s a m p l e , s + T i n d e x , s + T r e s i e v e , s ) , 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), T prog = s = s 0 ∑ d ( T transfer , s + T sample , s + T index , s + T resieve , s ) , 分别计入初始化或池迁移、补样、索引维护和继续筛法。这里 d d d
为理解低维阶段的开销，假设从头运行一次 s s s A c T s A c_T^s A c T s A > 0 A>0 A > 0 c T > 1 c_T>1 c T > 1
∑ s = s 0 d A c T s ≤ A c T d 1 − c T − 1 . \sum_{s=s_0}^{d}A c_T^s
\le \frac{A c_T^d}{1-c_T^{-1}}. s = s 0 ∑ d A c T s ≤ 1 − c T − 1 A c T d . 在这个简化模型下，逐维完整计算的总成本是末维成本的常数倍。这个式子只说明前面各维的开销尺度；复用是否加速，取决于它节省的后续筛法工作能否抵消迁移、补样与维护开销。
实验比较应固定输入基和最终长度质量或饱和目标，比较从头运行与渐进复用的总时间、峰值内存及阶段成本。检查次数、不同有效源对、不同结果和实际接纳数量，沿用重复配对、去重与有效覆盖 分别统计。
7. 与后续格约化策略的衔接
本篇先固定基，只讨论加维与复用。完整格约化还会插入短向量、改变基、缩小或移动窗口；这时需要同步处理整数系数和投影空间的变化，不能只修改窗口下标。
后续的 G6K/Pump 笔记将进一步组织这些操作，并结合投影格、BKZ 与局部 SVP 的 dimensions for free，区分筛法范围、提升范围和插入位置。
对于渐进加维后的概率建模，值得保留三个观察对象：归一化长度分布、新增方向的分量分布，以及新旧向量之间的夹角与约化概率。 它们连接本篇的确定性几何关系与后续的模型修正、选参和实验研究。
参考文献
1. Léo Ducas. Shortest vector from lattice sieving: A few dimensions for free . Advances in cryptology – EUROCRYPT 2018. 2018. DOI .
2. 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 .
![](data:image/svg+xml,%3Csvg xmlns="http://www.w3.org/2000/svg"/%3E)