DeepMind 扩散模型分解 68 位半素数，算力每加一位翻倍

Semiprime Factorization with Discrete Diffusion and Beam Search: Scaling Laws

Brendan O Donoghue, Nenad Tomasev, Volodymyr Mnih, Timothy Nguyen, Dalin Guo, Arun Nair, Kenneth Yang, Alexandre Frechette, Jasper Xian, Jean Tarbouriech, Pavel Tyletski, Ingrid von Glehn, Johannes Bausch, Demis Hassabis, Raia Hadsell

cs.LG

2026-11-07

DeepMind 用离散扩散加格后处理把学习式分解纪录从 56 位推到 68 位，但训练算力随位数指数增长，对 RSA 无威胁。

这篇在解决什么

RSA 的安全性押在一件事上：把两个大素数的乘积 n=p×q(半素数)拆回 p 和 q,计算上不可行。经典算法里最强的 GNFS 是亚指数复杂度，公开分解过的最大 RSA 模数停在 896 位；Shor 算法在量子机上多项式时间可解，但容错量子机还远。第三条路是让神经网络纯从数据学分解，不带任何数论先验。这条路此前最好成绩是 56 位(Freivalds 等人 2023 年，离散扩散)。DeepMind 这篇把纪录推到 68 位，更关键的是第一次把数据、模型大小、问题规模、推理算力四个维度的 scaling 律量了出来。

方法

问题被建模成条件生成：n、p、q 全部写成二进制，n 占 2k 位作为固定前缀，p、q 各 k 位全部打 mask,拼成 4k 长度的序列，由一个双向 Transformer 去噪器恢复。训练用离散扩散，用 mask 操作而非高斯噪声破坏 token 再学反向恢复。几个设计各自对应一个具体困难：

• 连续块 mask 而非逐位独立 mask。逐位 mask 时模型能靠局部插值蒙混，连续块强迫它处理进位传播和全局乘法约束。
• 自条件化。把上一步的软概率经门控 FFN 加回输入。过早吐硬 token 会丢掉连续不确定性，迭代修正就无从谈起。
• 两遍训练。第二遍在按推理分布重采样出的「已提交但可能有错」画布上训练，模型学会改错而不只是补全。
• 推理两级搜索。外层束搜索从 MSB 到 LSB 交替 commit p、q 的位；每个节点先跑 5 步内层 mini-denoising 校准分支概率，已 commit 的位在自条件化输入里被钳成 one-hot「oracle」嵌入；部分前缀若使 n 落出可行乘积区间，整支剪掉；到最深层剪枝退化为精确验证。MCTS 试过，实测不如束搜索。
• Coppersmith 后处理。基于 LLL 格归约，只要命中一个因子的高半位(k=34 时是 18 个 MSB),剩余位多项式时间补全。模型不必全对。

结果

参照物：30 位规模上，试除法最多 16,384 次除法保证全对，单次除法比一次去噪步便宜得多。ML 在自己能赢的规模上远慢于最古老的算法。

Scaling 律是真正的产出。数据维度是干净幂律；验证 NLL 有个 0.262 的门槛，一个只会抄可见位、传局部进位的非分解基线就能做到这个值，NLL 不穿过去分解率严格为 0,穿过去之后急剧上升。问题规模是主导维度：每加一位因子，同样 loss 需要约 2 倍训练步数。模型没有学出任何亚指数算法，学到的是带先验的暴力搜索。测试时算力上，已有非零成功率的模型，准确率随 log T 大致线性提升；本就为 0 的(68 位)加步数也还是 0。

68 位那 1 例要放在显微镜下看。模型在 4–16 位前缀上的 MSB 命中率约为随机猜的 3 倍，其中约 2.5 倍来自「把候选限制在乘积双曲线上」这个零学习先验，真正学出的集中度只有约 1.25 倍；过了第 4 位，每多一位命中率乘 0.52,与随机衰减一致。在 Coppersmith 门槛 18 位处，观测到 1 次命中，均匀随机期望 0.24 次、双曲线先验期望 0.62 次。这一例更接近幅度先验的尾部采样，不是可靠的算法性分解。

为什么重要

价值不在纪录，在测量。语言建模有平滑幂律和长度外推，因为语言有可复用的层次局部结构；半素数全局耦合、密码学伪随机，n 翻一位因子就混沌地变。没有可复用子结构，数据需求随位数指数涨。这等于给「学习式搜索能否啃下伪随机问题」一个带数字的否定答案，也顺带解释了语言的 scaling 曲线为什么不能直接外推到这类问题。

工程上可搬三件东西：验证比生成容易的领域，「束搜索+可行性剪枝+把已定决策当 oracle 条件」的两层搜索结构是通用的；先算出「不动脑基线」的 NLL 门槛再看模型有没有突破，这套诊断在任何约束生成任务里都能用；「近似生成+精确后处理」的组合值得在其他组合优化问题里找对应物。

局限与存疑

作者自述：计算效率远逊经典算法，对 RSA 无现在或可预见未来的威胁，scaling 近似 brute force。他们还点破一条：训练与测试共享同一个素数池，pair 级不重叠(排除了背答案)，但小位数下每个素数被见过数千次，「素数词汇」的记忆贡献剥不干净。

读下来另有两处。其一，68 位与 56 位不是同一种比较：此前 56 位是扩散模型直接恢复出因子，68 位这一例是祖先采样(T=500,无束搜索)在一个因子上给出 19 位前缀、Coppersmith 补完剩余 16 位，且统计上与先验尾部采样不可区分。纪录按论文自己的口径成立，含金量要打折。其二，模型大小维度的结论偏弱：2B 始终最好或并列最好，但 325M 与 1B 的排序在不同位数间来回翻转，这部分噪声论文没有解释。

术语

• 半素数(semiprime):两个素数的乘积；RSA 模数就是两个等长素数构成的平衡半素数。
• 离散扩散(discrete diffusion):用 mask 等离散操作而非高斯噪声破坏序列，再学反向恢复，适合强约束离散问题。
• Coppersmith 方法：基于 LLL 格归约，已知一个因子的高半位即可多项式时间补全其余位。
• 自条件化(self-conditioning):把模型上一步的软概率分布作为下一步输入，迭代推理时保留连续不确定性。
• GNFS:当前最强经典分解算法，亚指数复杂度，公开纪录为 896 位 RSA 模数。

原文与代码

• arXiv 2611.10202v1
• PDF
• Hugging Face

社区讨论

• DeepMind 用离散扩散+束搜索分解 68 位半素数，刷新纪录 weballergy
• DeepMind 论文:扩散模型+束搜索破解 68 位半素数,推得 scaling law IAmTimNguyen

相关论文

• 复用 MLP 做 fast weights,字节让 4B 模型免从头重训学会测试时训练
• 少步扩散做强化学习，可微奖励下梯度法最有效，加步数整体不涨
• 缩放相邻两层权重即可任意伪造锐度,Bengio 团队质疑平坦性假说
• 在线蒸馏容忍 200 倍失配,FP8 异步训练快 1.62 倍
• 拿探针当训练损失，Goodfire 把捷径学习、谄媚和 reward hacking 一并压住
• 一万条时序难样本上，结构化效应让 GPT-5.6 的相对 MASE 下降 40.7%

全部论文解读