通过自我对弈发现格基约简策略

# 通过自我博弈发现格约简策略  
来源：https://arxiv.org/html/2606.15301  

Mohamed Malhou  
FAIR, Meta Superintelligence Labs & Sorbonne Université CNRS, LIP6  
巴黎，法国  
mmalhou@meta\.com  

&Ludovic Perret  
EPITA, EPITA Research Lab \(LRE\)  
勒克雷姆兰-比塞特，法国  
ludovic\.perret@epita\.fr  

&Kristin Lauter  
FAIR, Meta Superintelligence Labs  
klauter@meta\.com  

###### 摘要  

Lenstra\-Lenstra\-Lovász \(LLL\) 算法是计算机科学中用于格基约简的开创性贡献，但其多项式时间输出的基向量随着维度的增加而远非最优。我们证明，深度强化学习可以通过与 LLL 的原始动作空间交互，发现严格更优、可泛化的约简策略。我们将格约简形式化为一个单人马尔可夫决策过程 \(MDP\)，并使用 AlphaZero 风格的自我博弈流水线训练一个深度残差网络，该流水线结合了自适应视界 MCTS（蒙特卡洛树搜索），将多步网络预测与熵门控扩展机制相结合。由此产生的策略Delta\-Star仅在小型88维qq\-ary格上训练，且需要的原始行操作少于 LLL。关键的是，它能够零样本泛化到未见过的模数和高达n=32n=32的更高维度，无需重新训练。

## 1 引言  

格约简是计算数学中的核心问题，支撑着现代算法数论、优化和密码学。现代基于格的密码方案——包括最近由 NIST 标准化用于后量子加密的方案\[6 (https://arxiv.org/html/2606.15301#bib.bib14)\]——的安全性依赖于在高维格中寻找短非零向量的假定困难性\[1 (https://arxiv.org/html/2606.15301#bib.bib16),33 (https://arxiv.org/html/2606.15301#bib.bib15),39 (https://arxiv.org/html/2606.15301#bib.bib11)\]。因此，理解格约简算法的实际限制对于评估这些密码系统的具体安全性至关重要\[15 (https://arxiv.org/html/2606.15301#bib.bib10)\]。实用格约简的主力工具是 Lenstra\-Lenstra\-Lovász \(LLL\) 算法\[25 (https://arxiv.org/html/2606.15301#bib.bib1)\]。LLL 是一个多项式时间算法，能够产生具有向量长度保证界限的基。它通过两个局部、原始的动作运作：*尺寸约简*，将向量对其前驱进行正交化；以及*相邻交换*，重新排序基。是否交换由 Lovász 条件决定，这是一个手工设计的启发式规则，确保特定势函数的单调递减。虽然 Lovász 条件足以保证多项式运行时间，但在实践中并非实现最强约简的最优策略。LLL 的平均情况行为众所周知难以分析，并且通常能产生比最坏情况界限所暗示的更好的基\[15 (https://arxiv.org/html/2606.15301#bib.bib10)\]。这一差距引出了一个自然的问题：*我们能否发现一个更好的 LLL 原始操作序列策略，使其比经典算法实现更强的约简？*  

最近的研究表明，深度强化学习 \(RL\) 结合蒙特卡洛树搜索 \(MCTS\)\[9 (https://arxiv.org/html/2606.15301#bib.bib17),23 (https://arxiv.org/html/2606.15301#bib.bib18)\] 可以发现超越手工设计启发式的算法。从复杂的棋盘游戏\[47 (https://arxiv.org/html/2606.15301#bib.bib21),48 (https://arxiv.org/html/2606.15301#bib.bib22),46 (https://arxiv.org/html/2606.15301#bib.bib23)\] 开始，这种方法已被改编用于发现矩阵乘法\[13 (https://arxiv.org/html/2606.15301#bib.bib24)\]、排序\[31 (https://arxiv.org/html/2606.15301#bib.bib27)\]、组合问题\[40 (https://arxiv.org/html/2606.15301#bib.bib25)\] 和形式数学推理\[20 (https://arxiv.org/html/2606.15301#bib.bib26)\] 的新算法。这些结果表明，当一个数学问题被表述为单人游戏\[43 (https://arxiv.org/html/2606.15301#bib.bib20)\] 时，RL 智能体可以探索可能的算法空间，并有可能识别出比手工设计更优的策略。  

与此同时，神经网络方法已被直接探索用于格约简。\[32 (https://arxiv.org/html/2606.15301#bib.bib30)\] 提出了一种自监督等变网络，输出分解的单模矩阵，在n=8n=8 的基准测试上实现了与 LLL 相当的性能，无需显式搜索。然而，将这种端到端方法扩展到更高维度仍然具有挑战性。  

在这项工作中，我们将 RL+MCTS 范式应用于格约简的核心机制。我们将格约简过程形式化为一个单人马尔可夫决策过程 \(MDP\)，将智能体限制在经典 LLL 算法的精确动作空间内：光标移动、尺寸约简和相邻交换。我们使用 AlphaZero 风格\[48 (https://arxiv.org/html/2606.15301#bib.bib22)\] 的自我博弈和一种新颖的自适应视界 MCTS 训练一个深度残差网络\[19 (https://arxiv.org/html/2606.15301#bib.bib48)\]，以发现一个替代刚性 Lovász 条件的数据驱动策略。我们的贡献如下：  

1. 1\.**格约简的 RL 形式化**。我们定义了一个匹配 LLL 局部动作空间的格约简 MDP，使得可以直接比较序列策略，而不会受到更丰富动作空间（如精确最短向量问题 \(SVP\) 预言机\[14 (https://arxiv.org/html/2606.15301#bib.bib49)\]）的混淆因素影响。  
2. 2\.**自适应视界 MCTS**。我们为 MCTS 引入了一种熵门控多步扩展机制，该机制使用预测策略的香农熵，允许搜索树跳过确定性延续并摊销推理调用。  
3. 3\.**在 LLL 自己的地盘上击败它**。我们学到的策略在使用 LLL 原始操作的情况下，在各种维度上比经典 LLL 算法实现了显著更好的根 Hermite 因子和正交性缺陷。  
4. 4\.**零样本泛化**。通过使用qq\-归一化观测张量和带有自适应池化输出特征的 Resnet 架构，我们的模型——仅在小型88维q=251q=251\-ary 格上训练——能够零样本泛化到n=32n=32 的维度和未见过的qq\(∼20−5000\\sim 20\-5000\)。

## 2 背景  

本节回顾格约简的数学基础，重点介绍 LLL 算法及其收敛保证与实际实现约简质量之间的差距。

### 2\.1 欧几里得格与基质量  

一个nn 维格L\\mathcal\{L\} 是Rn\\mathbb\{R\}^\{n\} 的一个离散加法子群，由nn 个线性无关的基向量B=\{b1,...,bn\}\\mathbf\{B\}=\\\{\\mathbf\{b\}\_\{1\},\\dots,\\mathbf\{b\}\_\{n\}\\\} 生成：  

L\(B\)=\{∑i=1nzibi:zi∈Z\}\.\\mathcal\{L\}\(\\mathbf\{B\}\)=\\left\\\{\\sum\_\{i=1\}^\{n\}z\_\{i\}\\mathbf\{b\}\_\{i\}:z\_\{i\}\\in\\mathbb\{Z\}\\right\\\}\.  

一个格有无穷多个基：B1\\mathbf\{B\}\_\{1\} 和B2\\mathbf\{B\}\_\{2\} 生成相同的格当且仅当B1=B2U\\mathbf\{B\}\_\{1\}=\\mathbf\{B\}\_\{2\}\\mathbf\{U\} 对于某个单模矩阵U∈Zn×n\\mathbf\{U\}\\in\\mathbb\{Z\}^\{n\\times n\}（det\(U\)=±1\\det\(\\mathbf\{U\}\)=\\pm 1\)。体积det\(L\)=\|det\(B\)\|\\det\(\\mathcal\{L\}\)=\|\\det\(\\mathbf\{B\}\)\| 是一个基不变量。

**qq\-ary 格**。一个整数格L⊆Zm\\mathcal\{L\}\\subseteq\\mathbb\{Z\}^\{m\} 对于模数q≥2q\\geq 2 是qq\-ary 的，如果qZm⊆L⊆Zmq\\mathbb\{Z\}^\{m\}\\subseteq\\mathcal\{L\}\\subseteq\\mathbb\{Z\}^\{m\}，因此成员关系仅取决于模qq 坐标。对于矩阵A∈Zqn×m\\mathbf\{A\}\\in\\mathbb\{Z\}\_\{q\}^\{n\\times m\}，原始qq\-ary 格定义为：  

Λq\(A\)=\{y∈Zm:∃s∈Zn,s⋅A≡y\(modq\)\}\.\\Lambda\_\{q\}\(\\mathbf\{A\}\)=\\\{\\mathbf\{y\}\\in\\mathbb\{Z\}^\{m\}:\\exists\\mathbf\{s\}\\in\\mathbb\{Z\}^\{n\},\\ \\mathbf\{s\}\\cdot\\mathbf\{A\}\\equiv\\mathbf\{y\}\\pmod\{q\}\\\}.\(1\)  

为了应用 LLL 或 BKZ 等格约简算法，我们需要Λq\(A\)\\Lambda\_\{q\}\(\\mathbf\{A\}\) 的一个显式满秩基。我们使用以下行式基矩阵将格嵌入到Zn\+m\\mathbb\{Z\}^\{n\+m\} 中：  

B=\[qIm0AIn\]∈Z\(n\+m\)×\(n\+m\)\.\\mathbf\{B\}=\\begin\{bmatrix\}q\\mathbf\{I\}\_\{m\}&\\mathbf\{0\}\\\\ \\mathbf\{A\}&\\mathbf\{I\}\_\{n\}\\end\{bmatrix\}\\in\\mathbb\{Z\}^\{\(n\+m\)\\times\(n\+m\)\}\.\(2\)  

B\\mathbf\{B\} 的行生成嵌入在Zn\+m\\mathbb\{Z\}^\{n\+m\} 中的Λq\(A\)\\Lambda\_\{q\}\(\\mathbf\{A\}\)，并且该构造确保qZn\+m⊆L\(B\)q\\mathbb\{Z\}^\{n\+m\}\\subseteq\\mathcal\{L\}\(\\mathbf\{B\}\)。

**基质量**。评估约简基的标准度量是*根 Hermite 因子*：  

δ0=\(‖b1‖det\(L\)1/n\)1/n，\\delta\_\{0\}=\\left\(\\frac\{\\\|\\mathbf\{b\}\_\{1\}\\\|\}\{\\det\(\\mathcal\{L\}\)^\{1/n\}\}\\right\)^\{1/n\}，\(3\)  

它衡量第一个基向量相对于格体积的短度。δ0\\delta\_\{0\} 越小表示约简越强。整个基的全局质量由*正交性缺陷*δ\(B\)=∏i‖bi‖/det\(L\)\\delta\(\\mathbf\{B\}\)=\\prod\_\{i\}\\\|\\mathbf\{b\}\_\{i\}\\\|/\\det\(\\mathcal\{L\}\) 捕获，当且仅当基正交时等于11（Hadamard 不等式\[17 (https://arxiv.org/html/2606.15301#bib.bib50)\]）。更多背景信息在附录A (https://arxiv.org/html/2606.15301#A1) 中提供。

### 2\.2 格拉姆-施密特正交化  

为了分析格基的几何形状，通常计算其格拉姆-施密特正交化 \(GSO\)。GSO 向量B~=\{b~1,...,b~n\}\\widetilde\{\\mathbf\{B\}\}=\\\{\\widetilde\{\\mathbf\{b\}\}\_\{1\},\\dots,\\widetilde\{\\mathbf\{b\}\}\_\{n\}\\\} 迭代定义如下：b~1=b1\\widetilde\{\\mathbf\{b\}\}\_\{1\}=\\mathbf\{b\}\_\{1\}，对于j\>1j\>1，  

b~j=bj−∑i=1j−1μi,jb~i，其中μi,j=⟨bj,b~i⟩⟨b~i,b~i⟩\.\\widetilde\{\\mathbf\{b\}\}\_\{j\}=\\mathbf\{b\}\_\{j\}-\\sum\_\{i=1\}^\{j\-1\}\\mu\_\{i,j\}\\widetilde\{\\mathbf\{b\}\}\_\{i\}，\\quad\\text\{其中\}\\quad\\mu\_\{i,j\}=\\frac\{\\langle\\mathbf\{b\}\_\{j\},\\widetilde\{\\mathbf\{b\}\}\_\{i\}\\rangle\}\{\\langle\\widetilde\{\\mathbf\{b\}\}\_\{i\},\\widetilde\{\\mathbf\{b\}\}\_\{i\}\\rangle\}\.\(4\)  

GSO 向量相互正交，并张成与原始基向量相同的子空间。

### 2\.3 LLL 算法  

Lenstra\-Lenstra\-Lovász \(LLL\) 算法\[25 (https://arxiv.org/html/2606.15301#bib.bib1)\] 通过两个局部、原始的动作运作：*尺寸约简*，确保 Gram\-Schmidt 系数满足\|μi,j\|≤1/2\|\\mu\_\{i,j\}\|\\leq 1/2；以及*相邻交换*，重新排序基向量。是否交换由 Lovász 条件决定：对于参数δ∈\(14,1\]\\delta\\in\(\\frac\{1\}\{4\},1\]，  

δ‖b~i‖2≤‖μi,i\+1b~i\+b~i\+1‖2\.\\delta\\\|\\widetilde\{\\mathbf\{b\}\}\_\{i\}\\\|^\{2\}\\leq\\\|\\mu\_\{i,i\+1\}\\widetilde\{\\mathbf\{b\}\}\_\{i\}\+\\widetilde\{\\mathbf\{b\}\}\_\{i\+1\}\\\|^\{2\}\.\(5\)  

当该条件被违反时，算法交换行ii 和i\+1i\+1 并使光标递减；否则前进。完整伪代码在算法1 (https://arxiv.org/html/2606.15301#alg1) 中给出。

**算法 1** LLL 算法  

**输入**: 基 B=\{b1,...,bn\}\\mathbf\{B\}=\\\{\\mathbf\{b\}\_\{1\},\\dots,\\mathbf\{b\}\_\{n\}\\\}，参数 δ∈\(14,1\]\\delta\\in\(\\frac\{1\}\{4\},1\]  
1: 计算 GSO 向量 B~\\widetilde\{\\mathbf\{B\}\} 和系数 μi,j\\mu\_\{i,j\}；设置 k←2k\\leftarrow 2  
2: **当** k≤nk\\leq n **时执行**  
3:   **对于** j=k−1,...,1j=k\-1,\\dots,1 **执行**  
4:     **如果** \|μj,k\|\>1/2\|\\mu\_\{j,k\}\|\>1/2 **则**  
5:       bk←bk−⌊μj,k⌉bj\\mathbf\{b\}\_\{k\}\\leftarrow\\mathbf\{b\}\_\{k\}-\\lfloor\\mu\_\{j,k\}\\rceil\\mathbf\{b\}\_\{j\}；更新 μi,k\\mu\_\{i,k\}（i≤ji\\leq j）\{SizeReduce\}  
6:     **结束如果**  
7:   **结束对于**  
8:   **如果** δ‖b~k−1‖2\>‖μk−1,kb~k−1\+b~k‖2\\delta\\\|\\widetilde\{\\mathbf\{b\}\}\_\{k\-1\}\\\|^\{2\}>\\\|\\mu\_\{k\-1,k\}\\widetilde\{\\mathbf\{b\}\}\_\{k\-1\}+\\widetilde\{\\mathbf\{b\}\}\_\{k\}\\\|^\{2\} **则**  
9:     交换 bk,bk−1\\mathbf\{b\}\_\{k\},\\mathbf\{b\}\_\{k\-1\}；更新 GSO 和系数；k←max⁡\(2,k−1\)k\\leftarrow\\max\(2,k\-1\) \{Swap\}  
10:   **否则**  
11:     k←k\+1k\\leftarrow k\+1  
12:   **结束如果**  
13: **结束当**  
14: **返回** LLL\-约简基 B\\mathbf\{B\}

通过势函数Φ\(B\)=∏i=1n‖b~i‖n−i\+1\\Phi\(\\mathbf\{B\}\)=\\prod\_\{i=1\}^\{n\}\\\|\\widetilde\{\\mathbf\{b\}\}\_\{i\}\\\|^\{n\-i\+1\} 保证终止，该函数在每次交换时严格递减。Lovász 条件是交换减少Φ\\Phi 的一个充分条件，但不一定是实现最强约简的最优序列策略。

**BKZ**。Schnorr 的 Block Korkine\-Zolotarev \(BKZ\) 算法\[45 (https://arxiv.org/html/2606.15301#bib.bib3),44 (https://arxiv.org/html/2606.15301#bib.bib2)\] 将 Lovász 条件推广到大小为β≥2\\beta\\geq 2 的块，以在β\\beta 指数复杂度的代价下实现更小的根 Hermite 因子。

## 3 Delta\-Star 的方法  

本节将格约简形式化为一个单人马尔可夫决策过程 \(MDP\)，介绍用于高效树搜索的自适应视界 MCTS 机制，并描述神经网络架构和分布式训练流水线。

### 3\.1 格约简作为单人游戏  

我们将latticeenv环境定义为一个情节性的确定性 MDP，其中智能体顺序操作格基以改善其质量。状态表示镜像了经典 LLL 算法的内部状态，同时跟踪当前基和一个行指针 \(光标\)kk。

**基采样与qq\-ary 格**。我们在qq\-ary 格上训练，这是密码学中使用的主要格族。对于基础维度nn，智能体操作一个2n×2n2n\\times 2n 矩阵。在训练期间，A\\mathbf\{A\} 的条目均匀采样自\[0,q−1\]\[0,q\-1\]。

**状态空间S\\mathcal\{S\}**。在时间步tt，状态sts\_\{t\} 由基矩阵Bt\\mathbf\{B\}\_\{t\}、其格拉姆-施密特正交化Bt∗\\mathbf\{B\}^\{\*\}\_\{t\}（见附录A (https://arxiv.org/html/2606.15301#A1)\)、格拉姆-施密特系数μt\\boldsymbol\{\\mu\}\_\{t\}、光标位置kt∈\{0,...,2n−1\}k\_\{t\}\\in\\\{0,\\dots,2n\-1\\\} 以及剩余步数组成。

**动作空间A\\mathcal\{A\}**。智能体从四个离散动作中选择，与 LLL（第̃2.3节 (https://arxiv.org/html/2606.15301#S2.SS3)）中可用的原始操作相同：

1. 1\.**MoveUp**：光标递减 k←max⁡\(1,k−1\)k\\leftarrow\\max\(1,k\-1\)。\# not allowed to be in k=0\\;\\texttt\{\# not allowed to be in \}k=0  
2. 2\.**MoveDown**：光标递增 k←min⁡\(2n−1,k\+1\)k\\leftarrow\\min\(2n\-1,k\+1\)。  
3. 3\.**Swap**：交换行 bk\\mathbf\{b\}\_\{k\} 和 bk−1\\mathbf\{b\}\_\{k\-1\}，然后更新 k←max⁡\(1,k−1\)k\\leftarrow\\max\(1,k\-1\)。  
4. 4\.**SizeReduce**：每当\|μk,j\|\>1/2\|\\mu\_\{k,j\}\|\>1/2 且 j\<kj\<k 时，从 bk\\mathbf\{b\}\_\{k\} 中减去前几行的整数倍。

**动作屏蔽**。当k\>1k\>1 时 MoveUp 可用，当k<2n−1k<2n\{\-\}1 时 MoveDown 可用，当k\>0k\>0 时 Swap 可用，SizeRed 始终可用。

**奖励**rt=log⁡M\(Bt\)−log⁡M\(Bt\+1\)log⁡M\(B0\)\+εr\_\{t\}=\\dfrac\{\\log M\(\\mathbf\{B\}\_\{t\}\)\-\\log M\(\\mathbf\{B\}\_\{t\+1\}\)\}\{\\log M\(\\mathbf\{B\}\_\{0\}\)\+\\epsilon\}

**状态**st\+1s\_\{t\+1\}：更新的Bt\+1\\mathbf\{B\}\_\{t\+1\}，k′k^\{\\prime\}，t\+1t\{\+\}1

**观测**ot\+1o\_\{t\+1\}（5×2n×2n\)\(5\\times 2n\\times 2n\)：  
Ch\. 0–2：Bt\+1/q\\mathbf\{B\}\_\{t\+1\}/q，Bt\+1∗/q\\mathbf\{B\}^\{\*\}\_\{t\+1\}/q，μt\+1\\boldsymbol\{\\mu\}\_\{t\+1\}  
Ch\. 3：时间  
Ch\. 4：指针kk

**终止？**t≥Tt\\geq T：继续，结束回合

图 1：用于 LLL 风格基约简的latticeenv环境。智能体控制一个指针kk指示当前行，具有四个局部动作。这模拟了经典 LLL 的顺序结构，并允许学习更好的序列策略。