GPU-Accelerated Graph-Colored Simulated Annealing for Integer Factorization

现代数字世界的许多安全性都建立在一个简单的数学技巧之上：将两个巨大的质数相乘极其容易，但仅通过观察结果来推断出使用了哪两个数字却非常困难。这种单向性是 RSA 加密算法的基础，该系统保护着在线银行、私人信息以及安全通信。几十年来，破解这一代码的唯一已知方法是尝试所有可能的数字组合，直到找到正确的一对，而对于大密钥而言，这项任务规模如此庞大，以至于即使是最强大的超级计算机也需要比宇宙寿命还要长的时间才能完成。虽然量子计算机承诺有一天能瞬间破解这一代码，但它们尚未准备好胜任这项工作。这留下了一个缺口，即经典计算机必须寻找一种新的方法来解决这个问题，不再是通过暴力破解，而是将寻找缺失数字的过程视为一个关于能量与平衡的谜题。

印度理工学院马德拉斯分校的研究人员开发了一种新方法来应对这一挑战，使用的是标准的图形处理器（GPU），即高端游戏和视频渲染电脑中常见的芯片。他们并没有直接尝试猜测数字，而是将问题转化为了一个由丘陵和山谷组成的景观，而解就在最深的山谷底部。他们将两个隐藏质数的比特映射到一个由微型开关组成的网格上，每个开关都可以处于两种状态之一。目标是找到这些开关的特定排列方式，从而创造出最低的能量状态，这种配置在数学上编码了那两个正确的质因数。

为了解决这个问题，该团队使用了一种称为模拟退火的技术，这种技术模仿了通过冷却金属以消除缺陷的物理过程。在他们的数字版本中，系统从随机的开关排列和高水平的“热量”开始，允许开关自由翻转。随着系统的冷却，开关会趋于一种更稳定的模式。研究人员设计了其软件以在单块强大的图形芯片 NVIDIA GH200 上运行，该芯片可以同时进行数千次计算。由于他们创建的数学地图大部分是空的——意味着大多数开关之间并不相互作用——他们组织了工作流程，使计算机只专注于实际存在的连接。这使得他们能够同时更新许多开关而不出错，这一成就需要一种巧妙的排序方法，以确保没有两个相互作用的开关在同一时刻被改变。

该系统并不总是能立即找到完美答案。在测试中，退火器始终能非常接近正确解，通常能达到真实数字的百分之几以内。为了弥补这最后的差距，研究人员增加了第二步：一个在计算机的最佳猜测值附近进行的引导搜索。他们使用了一种过滤方法来跳过那些不可能为质数的数字，从而大幅减少了所需的工作量。对于一个 100 位的数字，从初始设置到找到最终因数的整个过程，在单台机器上仅耗时六分多钟。这比传统方法显著更快，因为传统方法处理相同任务需要数小时。

研究人员在 16 到 128 位的数字上测试了他们的流水线。虽然他们成功在几分钟内分解了 100 位数字，但他们指出，该方法仍然依赖于最后的搜索步骤来找到确切答案。这个最后步骤的速度很大程度上取决于初始猜测值距离真相有多近。团队发现，他们的这种方法始终能提供比旧有的、更简单的猜测更好的起始点，这大大缩短了最终搜索所需的时间。他们还展示了使用一种被称为库珀史密斯（Coppersmith's）方法的特定数学技术可以进一步加速处理更大规模的数字，潜在地将 128 位数字的处理时间从数月缩短至数天。

这项工作并未破解当前的加密标准，因为测试的数字远小于现实世界安全中所使用的数字，后者通常涉及数百位的数字。然而，它证明了经典计算机在拥有正确的数学结构并针对并行处理进行优化时，可以比此前认为的更高效地解决这类问题。研究表明，瓶颈不再是计算机的原始速度，而在于初始猜测值可以被细化到何种程度。如果未来的改进能够让计算机更接近解，那么最终的搜索步骤可能会变得如此微小，以至于整个过程有一天可能会以多项式时间运行，这是一种会改变密码学格局的理论速度。目前，研究人员已经展示了通过尊重问题的独特形态并利用现代图形芯片的强大并行能力，将一个看似不可能的数学锁变成一个可解的谜题是完全可能的。