在显卡上分解一个155位数

把一个大数分解成质因数很难，而这种困难对密码学至关重要——这也是为什么论文特意说明了其结果不会威胁到什么。公开的“RSA挑战”数被用作因数分解方法的基准。RSA-155就是其中之一：155位十进制数，即512位二进制。

两种筛法，各有纪录

有两类算法占据主导地位。数域筛法是分解超大数的冠军：它早在1999年就分解了RSA-155；据论文介绍，目前的通用纪录是2026年分解的一个270位数RSA-896。更古老的二次筛法在渐近意义上更慢，用作者自己的话说，它是创造通用纪录的“错误工具”。不过，它也有自己的纪录榜：此前用它分解的最大的数是RSA-150，时间是2025年6月，耗费了11664个CPU核心小时。

二次筛法会搜寻大量能完全分解在一组小质数上的小数，然后用线性代数把它们组合成两个模N相等的平方数x²和y²。接着，求一次最大公约数就能找出一个因数。在计算机上，这对图形处理器（GPU）来说是一场噩梦：内存访问分散到远超任何缓存的范围，检验过程充满分支，而最后的代数运算采用一种没有任何厂商库支持的二进制算术。此前在GPU上的尝试只加速了其中个别步骤。

一切都在显卡上完成

德国帕德博恩大学数学研究所的Fabian Januszewski和Christoph Heinrichs开发了CUDA-MPQS，这是一个开源的二次筛法程序，其每一个阶段——准备多项式、筛选、检查候选、匹配部分结果、构建矩阵、求解矩阵以及最后开平方——都在GPU上运行。普通处理器只负责调度、初始化以及处理输入和输出；作者明确列出了少数仍在主机端执行的步骤。在一次100位数的测试中，GPU在99.9%的筛选时间里都处于忙碌状态，从不需要停下来等待处理器。

规模扩大后暴露出一个隐蔽的漏洞。在RSA-155的规模下，筛选过程中使用的一个8位计数器恰好在最有价值的候选上发生溢出，悄无声息地丢弃了其中98%至99.5%。团队用一个饱和计数器替换了它，并证明其结果完全相同。

约一天分解RSA-155

2026年7月14日，这套流程把RSA-155分解成了两个各有78位的质数，并在GPU和主机上分别进行了验证：

• 筛选：16个节点上的64张NVIDIA H100 GPU，用时10.8小时，收集了约1730万个关系式。
• 线性代数：单张H100用时10.9小时，处理一个1670万行、含6.84亿个非零元素的矩阵。
• 总计：700.6个GPU小时和242千瓦时，从开始到得出因数大约24小时。筛选占了成本的98.4%。

据作者所知，这是用二次筛法分解过的最大整数，比此前的纪录多出五位——而且是用该方法最简单的变体实现的：每个关系式只保留一个“大质数”，而近期的纪录使用的是三个。

比最好的处理器还快

对于一个100位数，单张H100只需29.2秒，一张消费级RTX 5070 Ti需要51秒。在对同一个数进行的受控比较中（两边都测量了能耗），一张H100比在AMD EPYC处理器96个核心上运行的最快CPU二次筛法快3.6至4.2倍，比另一个标准软件包快约九到十倍。他们还用302.9个GPU小时重新分解了RSA-150，而此前纪录用了11664个核心小时——作者强调，这个比例并不是同等条件下的加速比。

对加密不构成威胁

作者说得很明确：RSA-155早已被分解过，这并不是通用因数分解纪录，而且“这里没有任何东西缩小了安全余量”。该代码在设计上也被限制在约155位以内。他们的兴趣在别处：证明一种不规则、充满分支的算法可以完全运行在GPU上。他们指出，数域筛法核心的GPU格筛是下一个自然的目标——他们提到，其他人此后已经开始了这项工作，利用一个现有软件包的GPU移植版分解了RSA-260和RSA-896，其中后者是借助Claude完成的。

利益冲突。 作者声明使用了生成式AI和智能体编程工具：在软件开发中使用了Anthropic的Claude模型（通过Claude Code）以及OpenAI的GPT和Google的Gemini模型，在数据和稿件准备中使用了Claude模型。他们声明所有AI输出都经过了人工审核和验证。本文同样由Claude撰写。