量子因数分解：密码的终结？

因数分解的概念很简单：就是将一个数分解为质数的乘积。例如，15 可以分解为 3 和 5 的乘积。质数是指除了 1 和自身外不能被其他数整除的数，而合数则可以分解出比它小的因数。

因数分解为什么困难？

尽管分解小数很简单，大数因数分解却是一个经典难题。例如，21 很容易分解成 3 和 7，但对于一个像 2^67 −1 这样的21位数来说，要分解它则复杂得多。事实上，法国科学家梅森曾认为2^67 −1是质数，而这一错误观点在近 260 年后才被证明是错误的。

当分解一个大数时，计算量会随着位数指数增长。因数分解的一种传统方法是“逐一尝试”，即从小的质数开始尝试去除，这种方法的计算复杂度随着数位数的增加呈指数增长。

因数分解的困难特性被用在了现代密码学上。例如，我们常用的RSA 加密就是利用大数因数分解的难度来确保信息的安全性。当前的 RSA 加密体系通常使用数百位的整数作为密钥。也就是说，正是因数分解的困难性，保证了我们的网购、银行转账等日常活动的安全性。

量子计算打破因数分解的时间壁垒

1994 年，美国数学家 彼得·肖尔（Peter Shor） 提出了著名的“量子因数分解算法”，即Shor 算法。这种算法的计算量随着数字位数的增长呈多项式增长，而不是经典算法的指数增长。因此，量子因数分解相较于经典方法会大幅加速。

量子计算在因数分解方面的潜力究竟有多大呢？假设经典计算机和量子计算机都每秒能执行一万亿次运算，用它们来分解一个 300 位的数，经典计算机可能需要 15 万年，而量子计算机不到一秒；如果分解一个 5,000 位的数，经典计算机需要 50 亿年，而量子计算机只需 2 分钟！因此，如果量子计算机能够大规模投入使用，当前的 RSA 密码系统将几乎瞬间被破解。

尽管量子算法已经实现了理论上的突破，但量子计算机的硬件目前还没有达到能广泛应用的水准。目前，量子计算机分解的最大数是291,311，它由中国科学技术大学的杜江锋院士和彭新华教授在2017年实现。这个数仅是一个 6 位数（约 19 位二进制），而我们常用的 RSA 密钥长度是 1,024 位。因此，量子计算机在分解实际应用中的大数方面仍有很长的路要走。

未来不再安全的密码

量子计算带来的安全威胁不仅限于 RSA 加密。另一种常用的椭圆曲线加密也面临同样的风险。椭圆曲线加密基于离散对数问题，而离散对数问题在量子计算中同样可以通过 Shor 算法来解决。比特币的加密基础正是基于椭圆曲线密码，因此在量子计算面前也有潜在的风险。

量子计算机是否会击破所有基于数学的密码？目前尚无定论。量子密码学可能提供一种无法被量子计算破解的安全体系，但它的应用仍在研究和开发中。可以确定的是，量子计算机对现有基于数学的加密方法构成了严峻挑战，各国正在积极研究如何在这一即将到来的量子时代确保信息安全。

作者：《你也可以理解量子信息》风云际会

审核：罗会仟 中科院物理所研究员

文章由科普中国-创作培育计划出品，转载请注明来源。