For AI agents: the complete documentation index is available at https://shijin.space/llms.txt, the full documentation bundle is available at https://shijin.space/llms-full.txt, and this page is available as Markdown at https://shijin.space/knowledge/g6k-and-pump/index.md.
ShiJin

    26 G6K 与 Pump

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

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

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

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

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

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

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

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

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

    向左扩展、向右扩展、向左缩窗、筛法和插入，都是对这些状态的操作。状态定义见 G6K，EUROCRYPT 2019，§3.3，PDF 第 11 页。

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

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

    第 25 篇已经说明，对 y∈Λ[ℓ,r]y\in\Lambda_{[\ell,r]} 向左逐步做 Babai 提升，可以在位置 p≤ℓp\le\ell 得到

    y~p=y+∑k=pℓ−1εkbk∗,∣εk∣≤12.\widetilde y_p = y+\sum_{k=p}^{\ell-1}\varepsilon_k b_k^*, \qquad |\varepsilon_k|\le\tfrac12.

    由正交性，

    ∥y~p∥2=∥y∥2+∑k=pℓ−1εk2gk2,gk=∥bk∗∥.\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 说明。

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

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

    Q(p)=log⁡gp2∥cp∥2−(p−a)log⁡τ,τ≥1,\boxed{ Q(p)= \log\frac{g_p^2}{\|c_p\|^2} -(p-a)\log\tau, \qquad \tau\ge1, }

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

    这与官方 scoring_down 的排序一致，位置偏移 aa 只增加公共常数；本文用 τ\tau 表示原论文的插入偏好参数 θ\theta，以免与前文的夹角混淆。参见固定版本的评分实现。该评分是策略选择，不保证整个 GSO 轮廓的改善最优。

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

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

    πp(w)=cp,y=πℓ(w)≠0.\pi_p(w)=c_p, \qquad y=\pi_\ell(w)\ne0.

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

    span⁡(b1′,…,bℓ′)=span⁡(b1,…,bℓ−1,w).\boxed{ \operatorname{span}(b'_1,\ldots,b'_\ell) = \operatorname{span}(b_1,\ldots,b_{\ell-1},w). }

    这对应 G6K §3.2 的式 (4)，PDF 第 10 页。它表示：新基投影掉的空间，是旧前缀空间再加上候选方向。

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

    x′=πℓ+1′(x)=x−⟨x,y⟩∥y∥2y∈Λ[ℓ+1,r]′.\boxed{ x'=\pi'_{\ell+1}(x) =x-\frac{\langle x,y\rangle}{\|y\|^2}y \in\Lambda'_{[\ell+1,r]}. }

    这里用到 xx 与旧前缀空间正交，而 yy 是 ww 在该正交补中的分量。进一步有

    ∥x′∥2=∥x∥2−⟨x,y⟩2∥y∥2≤∥x∥2.\|x'\|^2 = \|x\|^2-\frac{\langle x,y\rangle^2}{\|y\|^2} \le\|x\|^2.

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

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

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

    官方 insert 实现要求候选在筛法区间内至少有一个系数为 ±1\pm1，以完成其支持的插入与池变换；这比一般的“整数系数整体互素”更具体。参见固定版本的 insert 与 split_lll 实现。

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

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

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

    ℓmin⁡=a+f,smax⁡=β−f.\ell_{\min}=a+f, \qquad \boxed{s_{\max}=\beta-f.}

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

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

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

    下面是省略提前退出细节的示意流程。初始筛法维数 s0s_0 满足 1≤s0≤β−f1\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 函数。因此，达到目标后可能提前结束，实际峰值维数可以小于 β−f\beta-f。

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

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

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

    f0>f1>⋯ ,smax⁡,t=β−ft.f_0>f_1>\cdots, \qquad s_{\max,t}=\beta-f_t.

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

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

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

    a0, a0+J, a0+2J, …,a_0,\ a_0+J,\ a_0+2J,\ \ldots,

    首尾部分另行处理窗口和维数。更大的 JJ 减少调用位置，但是否节省达到同一约化质量的时间，还取决于块范围、ff、插入效果和 tour 次数。参见官方 BKZ 调度实现。

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

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

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

    TPump=Tsieve+Tlift+Tbasis+Tmaint.T_{\mathrm{Pump}} = T_{\mathrm{sieve}} +T_{\mathrm{lift}} +T_{\mathrm{basis}} +T_{\mathrm{maint}}.

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

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

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

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

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

    引用此笔记