1991 年，位于马萨诸塞州贝德福德的网络安全公司 RSA Laboratories 发布了一系列 54 个越来越大的数字，这些数字是通过将两个素数相乘而生成的。然后，该公司向计算机科学界发出了挑战，要求他们将这些数字进行因式分解——找出每个数字的原始素数。该公司甚至为其中一些解决方案提供了现金奖励。
这项挑战旨在评估最先进的数字因式分解能力。这很重要，因为因式分解——或者更确切地说，其难度——确保了各种公钥密码系统的安全。因此，先进的因式分解能力会降低这些密码系统的安全性。
挑战于 2007 年结束，但即使在今天，这些 RSA 数字中仍有 31 个未被因式分解。其中最大的是 RSA-2048，之所以这样命名是因为表示它所需的位数。
人们很容易认为数字因式分解的进展已经停滞。但暗地里，一场革命正在酝酿，那就是功能日益强大的量子计算机，它们在因式分解方面比传统计算机要好得多。
目前，这些机器的威力还不足以超越最强大的传统计算机。这引出了一个问题：它们何时才能做到？
量子算法
今天，得益于中国数学工程与先进计算国家重点实验室的 Bao Yan 及其同事的研究，我们得到了答案。他们开发出了一种方法，可以大幅提升能够因式分解数字的量子算法的威力。
他们利用自己的方法，增加了量子计算机能够因式分解的最大数字的尺寸。他们表示，他们的工作为量子计算机破解“加密重要性”的代码（例如 RSA-2048）铺平了道路。
公钥密码系统的安全性取决于因式分解这个数学过程，它是乘法的逆运算。乘法和因式分解的有趣之处在于，尽管它们密切相关，但执行起来却截然不同。
将两个素数相乘得到一个更大的数字很容易。但是，从一个大数开始，找出它的素数因子却很难。事实上，随着数字的增大，难度会呈指数级增长，而且很容易制造出一个大到足以让一台经典计算机花费宇宙寿命才能找到其因子的数字。
这正是公钥密码系统如此安全的原因——它们并非完美，但一台传统计算机需要宇宙的寿命才能破解它们。
这种想法在 1994 年发生了改变，当时美国数学家 Peter Shor 提出了一种量子算法，该算法可以比经典算法更快地因式分解数字。Shor 的工作一举打破了人们的幻想，即未来任何公钥密码系统都可能被量子计算机破解。
Shor 算法的潜力一直是量子计算机发展的主要驱动力。但其实现起来却很棘手，因为它需要比现有量子计算机强大得多的量子计算机。
使用 Shor 算法，量子计算机能够因式分解的最大数字仅为 21。其他方法更为成功，但远不足以处理 RSA 数字。“在真实的物理系统中，使用通用方法因式分解的最大整数是 249919，”Bao 及其同事说道。
这个数字可以用 18 位来表示。然而，现代公钥密码系统依赖于大得多的数字，可以用 2048 位或更多位来表示。这就是为什么这些密码系统看起来可以免受此类攻击的原因，但一个重要的问题是，量子计算机还需要多久才能处理它们。
量子-经典混合
Bao 及其同事取得的突破是加速了 Shor 算法的一种替代方法，称为 Schnorr 算法（sic）。这是一种经典的算法，包含多个需要时间来解决的步骤。
Bao 及其同事的方法是使用量子优化算法来加速最耗时的步骤。这种量子-经典混合方法的效果是大大加快了因式分解过程，但所需的量子计算机的威力却比 Shor 算法所需的要小。
结果令人印象深刻。Bao 及其同事利用他们的这种方法，使用一台仅有十个量子比特的超导量子计算机，成功因式分解了 48 位数字 261980999226229。Bao 及其同事称：“这是在真实的量子设备上使用通用方法因式分解的最大整数。”
所有这一切意味着因式分解更大数字的前景是光明的。Bao 及其同事计算，他们的这种方法可以用 372 个量子比特的量子计算机来因式分解 RSA-2048。
“如此规模的量子资源很可能在不久的将来实现，”他们说。事实上，IBM 最近就推出了一款拥有 433 个量子比特的量子计算机。
然而，有一个重要的注意事项。决定量子计算机能力的不仅仅是量子比特的数量，还有它的错误率，目前，量子计算机的错误率太高，无法进行有利润的大规模计算。
尽管如此，Bao 及其同事的工作非常有趣，表明 RSA 数字很可能在不久的将来像多米诺骨牌一样倒下。历时 30 多年，RSA 因式分解挑战可能终于接近被攻克。
这对仍然广泛使用的公钥加密系统的安全性具有显而易见的影响。自 Shor 发表声明以来，密码学家们已经有充足的时间来研究更安全的通信方法。他们是否成功，应该很快就会揭晓。
参考：《使用亚线性资源在超导量子处理器上因式分解整数》：arxiv.org/abs/2212.12372
