# 26 G6K 与 Pump

整理日期：2026-10-17。  
适用范围：G6K 的状态组织、动态提升与基插入，Pump 的升维与降维流程，以及它与 WorkOut、BKZ 的关系。  
前置笔记：[16 投影格、BKZ 与局部 SVP](/knowledge/projected-lattices-bkz-and-local-svp/)、[25 渐进筛法与向量池复用](/knowledge/progressive-sieving-and-vector-pool-reuse/)。

沿用列基 $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 控制层。参见[项目说明](https://github.com/fplll/g6k)。

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

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

向左扩展、向右扩展、向左缩窗、筛法和插入，都是对这些状态的操作。状态定义见 [G6K，EUROCRYPT 2019，§3.3，PDF 第 11 页](https://ir.cwi.nl/pub/28539/2019-089.pdf)。

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

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

第 25 篇已经说明，对 $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（动态提升）** 在筛法运行过程中，对符合提升条件的已访问向量尝试提升，并更新各位置的候选；这些向量不必留在最终池中。实际提升受长度阈值等参数控制，不能理解为对每个检查过的向量对都完整提升。相关控制见[官方实现的 otf_lift 与 lift_radius 说明](https://github.com/fplll/g6k#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$ 只增加公共常数；本文用 $\tau$ 表示原论文的插入偏好参数 $\theta$，以免与前文的夹角混淆。参见[固定版本的评分实现](https://github.com/fplll/g6k/blob/c71e084dd003e1ffbfe8c91a7211b0ce9da22245/g6k/algorithms/pump.py#L86-L89)。该评分是策略选择，不保证整个 GSO 轮廓的改善最优。

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

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

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

第 16 篇说明，基插入需要保持原格的幺模换基。为了继续复用池，G6K 还要求换基保持特定的前缀空间关系：

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

这对应 [G6K §3.2 的式 (4)，PDF 第 10 页](https://ir.cwi.nl/pub/28539/2019-089.pdf)。它表示：新基投影掉的空间，是旧前缀空间再加上候选方向。

对旧池中的 $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.
$$

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

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

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

官方 insert 实现要求候选在筛法区间内至少有一个系数为 $\pm1$，以完成其支持的插入与池变换；这比一般的“整数系数整体互素”更具体。参见[固定版本的 insert 与 split_lll 实现](https://github.com/fplll/g6k/blob/c71e084dd003e1ffbfe8c91a7211b0ce9da22245/g6k/siever.pyx)。

**插入位置 $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$：

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

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

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

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

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

    返回更新后的基
~~~

论文给出完整的抽象升降序列；上述流程采用非空初始窗口，并允许按指定条件结束下降。参见 [G6K §4.1，式 (10)，PDF 第 12–13 页](https://ir.cwi.nl/pub/28539/2019-089.pdf)。

实际控制还包括初始维数、目标长度、时间限制、下降插入范围和饱和异常处理，见[官方 pump 函数](https://github.com/fplll/g6k/blob/c71e084dd003e1ffbfe8c91a7211b0ce9da22245/g6k/algorithms/pump.py#L92-L180)。因此，达到目标后可能提前结束，实际峰值维数可以小于 $\beta-f$。

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

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

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

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

先前调用改善基，为后续更大维数的搜索提供预处理。减小 $f$ 的步长和目标长度决定调用安排；达到目标可以停止。参见[官方 workout 函数](https://github.com/fplll/g6k/blob/c71e084dd003e1ffbfe8c91a7211b0ce9da22245/g6k/algorithms/workout.py)。

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

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

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

首尾部分另行处理窗口和维数。更大的 $J$ 减少调用位置，但是否节省达到同一约化质量的时间，还取决于块范围、$f$、插入效果和 tour 次数。参见[官方 BKZ 调度实现](https://github.com/fplll/g6k/blob/c71e084dd003e1ffbfe8c91a7211b0ce9da22245/g6k/algorithms/bkz.py)。

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

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

沿用第 25 篇的成本分解，一次 Pump 的时间可以按互不重叠的工作类别记录为

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

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

比较策略时，至少记录最大筛法维数、峰值池大小、总时间和最终质量，并说明 $f$、下降再筛及外层调用安排。[第 24 篇](/knowledge/duplicate-pairs-and-effective-coverage/)的数据库接纳计数也不能替代这里的基插入次数。

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

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

本文的实现细节核对至 2026-10-17，源码固定为提交 [c71e084](https://github.com/fplll/g6k/commit/c71e084dd003e1ffbfe8c91a7211b0ce9da22245)；论文定义与该实现的控制选项分别引用。

## 引用此笔记

- [27 筛法的并行化与平台成本模型](/knowledge/parallel-lattice-sieving-and-platform-costs/)