↓ 跳过正文
ShiJin

26 G6K 与 Pump

Markdown 版本

目录

整理日期：2026-10-17。
适用范围：G6K 的状态组织、动态提升与基插入，Pump 的升维与降维流程，以及它与 WorkOut、BKZ 的关系。
前置笔记：16 投影格、BKZ 与局部 SVP、25 渐进筛法与向量池复用。

沿用列基 \(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 控制层。参见项目说明。

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

  • 当前基及 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 页。

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

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 说明。

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

对满足插入条件且 \(\|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\)，以免与前文的夹角混淆。参见固定版本的评分实现。该评分是策略选择，不保证整个 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 页。它表示：新基投影掉的空间，是旧前缀空间再加上候选方向。

对旧池中的 \(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 实现。

插入位置 \(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：
            在当前窗口继续筛法并维护提升候选
        否则：
            调整池大小，继续考察可用候选

    返回更新后的基

论文给出完整的抽象升降序列；上述流程采用非空初始窗口，并允许按指定条件结束下降。参见 G6K §4.1，式 (10)，PDF 第 12–13 页。

实际控制还包括初始维数、目标长度、时间限制、下降插入范围和饱和异常处理，见官方 pump 函数。因此，达到目标后可能提前结束，实际峰值维数可以小于 \(\beta-f\)。

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

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

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

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

先前调用改善基，为后续更大维数的搜索提供预处理。减小 \(f\) 的步长和目标长度决定调用安排；达到目标可以停止。参见官方 workout 函数。

这里需要区分两种复用：一次 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 调度实现。

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

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

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

$$ T_{\mathrm{Pump}}
#

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

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

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

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

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

本文的实现细节核对至 2026-10-17，源码固定为提交 c71e084；论文定义与该实现的控制选项分别引用。

引用此笔记
#