G6K 与 Pump

沿用列基 $B=(b_1,\ldots,b_n)$ 、投影 $\pi_i$ 和局部格 $\Lambda_{[i,j]}$ 。下标从 $1$ 开始，区间包含两端。本篇允许基随插入而变化；带撇号的量对应新基。

记提升窗口为 $[a,r]$ ，当前筛法窗口为 $[\ell,r]$ ，其中 $a\le\ell\le r$ ，并令

\beta=r-a+1,\qquad s=r-\ell+1.

$\beta$ 是本次 Pump 的实际块维数， $s$ 是当前筛法维数。论文和代码使用从 $0$ 开始、右端点不包含在内的区间；本文的 $(a,\ell,r)$ 对应代码中的 $(a-1,\ell-1,r)$ 。

1. G6K：把筛法组织成可连续操作的状态

G6K（General Sieve Kernel）提供组织筛法与格约化的框架及实现。 其中的筛法内核负责在当前窗口内搜索短向量，上层策略决定窗口如何变化、何时提升和插入。官方实现提供 C++ 内核与 Python 控制层 [1]。

理解它时，需要同时跟踪四类状态：

当前基及 GSO： 确定整数系数如何对应几何向量。
窗口位置 $a,\ell,r$ ： 分别界定提升范围与筛法范围。
向量池 $D\subseteq\Lambda_{[\ell,r]}\setminus\{0\}$ ： 保存供当前筛法使用的向量。
各位置的提升候选 $c_p$ ： 对 $a\le p\le\ell$ ，记录在 $\Lambda_{[p,r]}$ 中找到的可供插入的短向量；某个位置也可能尚无候选。

向左扩展、向右扩展、向左缩窗、筛法和插入，都是对这些状态的操作 [2, p. 11]。

因此，检查一次操作是否正确，需要同时检查基、窗口、向量表示和候选是否仍然对应。

2. 动态提升：从筛法候选到插入候选

渐进筛法已经说明，对 $y\in\Lambda_{[\ell,r]}$ 向左逐步做 Babai 提升，可以在位置 $p\le\ell$ 得到

\widetilde y_p = y+\sum_{k=p}^{\ell-1}\varepsilon_k b_k^*, \qquad |\varepsilon_k|\le\tfrac12.

由正交性，

\boxed{ \|\widetilde y_p\|^2 = \|y\|^2+\sum_{k=p}^{\ell-1}\varepsilon_k^2g_k^2, \qquad g_k=\|b_k^*\|. }

投影长度与提升后的长度具有不同排序。某条向量在当前池中不够短，仍可能因提升残差较小而成为有用的插入候选。

G6K 的 on-the-fly lifting（动态提升） 在筛法运行过程中，对符合提升条件的已访问向量尝试提升，并更新各位置的候选；这些向量不必留在最终池中。实际提升受长度阈值等参数控制 [1, sec. Other CLI programs and commands]。这不意味着对每个检查过的向量对都要完整提升。

这使两种选择可以分开：向量池按当前筛法空间中的规则更新；基插入按提升后的效果选择。

对满足插入条件且 $\|c_p\|^2<g_p^2$ 的候选，可以使用评分

\boxed{ Q(p)= \log\frac{g_p^2}{\|c_p\|^2} -(p-a)\log\tau, \qquad \tau\ge1, }

并选择得分最大的候选。第一项衡量局部平方长度改善；第二项在 $\tau>1$ 时偏好较靠左的位置。

这与官方 scoring_down 的排序一致，位置偏移 $a$ 只增加公共常数 [3, ll. 86–89]。本文用 $\tau$ 表示原论文的插入偏好参数 $\theta$ ，以免与前文的夹角混淆。该评分是策略选择，不保证整个 GSO 轮廓的改善最优。

3. 插入后，向量池怎样继续使用

假设选定位置 $p\in[a,\ell]$ ，把候选提升为原基的整数线性组合 $w$ ，使

\pi_p(w)=c_p, \qquad y=\pi_\ell(w)\ne0.

投影格、BKZ 与局部 SVP说明，基插入需要保持原格的幺模换基。为了继续复用池，G6K 还要求换基保持特定的前缀空间关系：

\boxed{ \operatorname{span}(b'_1,\ldots,b'_\ell) = \operatorname{span}(b_1,\ldots,b_{\ell-1},w). }

新基投影掉的空间由旧前缀空间和候选方向共同张成 [2, p. 10]。

对旧池中的 $x\in\Lambda_{[\ell,r]}$ ，由上述空间关系直接推得

\boxed{ x'=\pi'_{\ell+1}(x) =x-\frac{\langle x,y\rangle}{\|y\|^2}y \in\Lambda'_{[\ell+1,r]}. }

这里用到 $x$ 与旧前缀空间正交，而 $y$ 是 $w$ 在该正交补中的分量。进一步有

\|x'\|^2 = \|x\|^2-\frac{\langle x,y\rangle^2}{\|y\|^2} \le\|x\|^2.

因此，一次符合上述条件的插入可以同时完成：

通过换基改善基。
将旧池投影到新基下的较小窗口。
将筛法维数从 $s$ 降为 $s-1$ ，继续使用得到的池。

实际更新还要同步整数系数、GSO 和缓存，并处理零向量与重复。绝对长度不增，也不保证新池已满足当前窗口的饱和要求。

官方 insert 实现要求候选在筛法区间内至少有一个系数为 $\pm1$ ，以完成其支持的插入与池变换；这比一般的“整数系数整体互素”更具体 [4, insert and split_lll]。

插入位置 $p$ 与筛法左边界 $\ell$ 是不同的量。 即使插入发生在 $p<\ell$ ，操作完成后的筛法窗口仍变为新基下的 $[\ell+1,r]$ 。

4. Pump：先升维搜索，再插入并降维

设预留的 dimensions for free 数量为 $f$ ，其中 $0\le f<\beta$ 。按计划运行到顶点时，

\ell_{\min}=a+f, \qquad \boxed{s_{\max}=\beta-f.}

$f$ 描述顶点时筛法窗口与提升窗口的差；在其他阶段，两者的维数差为 $\ell-a$ 。

Pump-up： 固定右端点 $r$ ，逐步减小 $\ell$ 。每次向左扩展后继续筛法，并维护提升候选。

Pump-down： 选择候选插入基，将池转到较小的投影窗口；没有合适候选时，直接向左缩窗。下降时可以继续筛法，也可以只保留和调整池。

下面是省略提前退出细节的示意流程。初始筛法维数 $s_0$ 满足 $1\le s_0\le\beta-f$ ：

Pump(B, a, r, f, s₀, down_sieve):
    清空旧池，对目标块做预处理
    ℓ ← r − s₀ + 1
    初始化当前窗口，筛法并维护提升候选

    # 上升：逐步增加筛法维数
    当 ℓ > a + f：
        向左扩展一次，ℓ ← ℓ − 1
        筛法并维护提升候选

    # 下降：在改善基的同时减小筛法维数
    当 ℓ < r 且未达到下降停止条件：
        按当前评分规则选择可插入候选

        如果存在：
            插入候选，变换池与相关状态
            ℓ ← ℓ + 1
            # 成功插入已经降维，不再额外执行缩窗
        否则：
            向左缩窗一次，ℓ ← ℓ + 1

        如果 down_sieve：
            在当前窗口继续筛法并维护提升候选
        否则：
            调整池大小，继续考察可用候选

    返回更新后的基

论文给出完整的抽象升降序列 [2, pp. 12–13]。上述流程采用非空初始窗口，并允许按指定条件结束下降。

实际控制还包括初始维数、目标长度、时间限制、下降插入范围和饱和异常处理 [3, ll. 92–180]。因此，达到目标后可能提前结束，实际峰值维数可以小于 $\beta-f$ 。

下降再筛提供了补充候选和改善当前池的机会，也增加工作量；是否启用，应按最终约化质量与总耗时比较。

5. WorkOut 与 BKZ：在 Pump 外层安排工作

WorkOut 在同一个目标块上安排多次 Pump。 逐步减小 $f$ ，对应逐步提高允许的最大筛法维数：

f_0>f_1>\cdots, \qquad s_{\max,t}=\beta-f_t.

先前调用改善基，为后续更大维数的搜索提供预处理。减小 $f$ 的步长和目标长度决定调用安排；达到目标可以停止 [5, workout]。

这里需要区分两种复用：一次 Pump 内复用向量池；多次 Pump 之间保留改善后的基。 本次核对的标准 pump 实现在每次开始时清空数据库，不能把 WorkOut 理解为始终携带同一个池逐渐加维。

BKZ 在不同局部块之间安排调用。 简单方案在各位置调用 WorkOut；Pump-and-Jump 则按步长 $J\ge1$ 移动起点，在相应位置调用 Pump。内部区间的起点可写为

a_0,\ a_0+J,\ a_0+2J,\ \ldots,

首尾部分另行处理窗口和维数 [6]。更大的 $J$ 减少调用位置，但是否节省达到同一约化质量的时间，还取决于块范围、 $f$ 、插入效果和 tour 次数。

对应的层次是：筛法内核处理当前池，Pump 组织一次局部升降过程，WorkOut 安排同一块上的多次 Pump，BKZ 调度不同块。

6. 成本、停止条件与后续研究

沿用渐进筛法的成本分解，一次 Pump 的时间可以按互不重叠的工作类别记录为

T_{\mathrm{Pump}} = T_{\mathrm{sieve}} +T_{\mathrm{lift}} +T_{\mathrm{basis}} +T_{\mathrm{maint}}.

分别对应筛法内核、提升与候选比较、预处理及插入换基、窗口迁移与池维护；动态提升若已包含在内核计时中，汇总时应避免重复计入。

比较策略时，至少记录最大筛法维数、峰值池大小、总时间和最终质量，并说明 $f$ 、下降再筛及外层调用安排。去重与有效覆盖的数据库接纳计数也不能替代这里的基插入次数。

停止条件继续沿用筛法的基本框架与两向量约化的区别：找到满足长度目标的向量、达到启发式饱和度、耗尽计算预算，分别说明不同的结果。完成一次 Pump 或一轮 BKZ，不自动证明已得到精确 SVP 解或精确 HKZ/BKZ 约化基。

本篇属于筛法专题基础。后续研究增量可围绕具体基线，记录插入评分、 $f$ 的选择、下降再筛或跨调用复用的改进，并在相同长度或基质量目标下核对收益。

参考文献

1. G6K Team. G6K: The general sieve kernel. 原文.

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.

3. G6K Team. G6K: g6k/algorithms/pump.py. 原文.

4. G6K Team. G6K: g6k/siever.pyx. 原文.

5. G6K Team. G6K: g6k/algorithms/workout.py. 原文.

6. G6K Team. G6K: g6k/algorithms/bkz.py. 原文.

G6K 与 Pump#

#1. G6K：把筛法组织成可连续操作的状态

#2. 动态提升：从筛法候选到插入候选

#3. 插入后，向量池怎样继续使用

#4. Pump：先升维搜索，再插入并降维

#5. WorkOut 与 BKZ：在 Pump 外层安排工作

#6. 成本、停止条件与后续研究

#参考文献