在经典计算机的世界里，大数分解是一个令人望而生畏的难题。给你一个 2048 位的整数，让你找出它的两个质因数——用目前最快的超级计算机，也需要数万年。这正是 RSA 安全的根基：正向运算（乘法）容易，逆向运算（分解）极其困难。
然而，1994 年，一位数学家彼得·肖尔（Peter Shor）提出了一种算法，证明如果有一台足够强大的量子计算机，它可以在几秒钟内完成大数分解。这个发现像一颗炸弹，震动了整个密码学界。为什么量子计算机能做到经典计算机做不到的事？答案藏在量子物理的奇特性质里。
从比特到量子比特（Qubit）
经典计算机的“比特”只有两种状态：0 或 1。一个比特一次只能代表一个数字。要尝试 2^n 种可能性，经典计算机需要串行地一个个试，或者用无数个核心并行，但数量有限。
量子比特则完全不同。利用叠加原理，一个量子比特可以同时处于 0 和 1 的叠加态。两个量子比特可以同时处于 00、01、10、11 四种状态的叠加。n 个量子比特可以同时表示 2^n 种状态。这意味着，量子计算机在某种程度上可以“并行”处理海量的可能性，而不是一个个地试。
但仅仅有叠加还不够。量子计算机还需要纠缠——两个量子比特之间可以建立关联，测量一个会瞬间影响另一个。纠缠让量子算法能够把计算中的关联性利用起来，实现经典算法无法企及的效率。
Shor 算法的核心思想
Shor 算法不是暴力破解，而是一种巧妙的数学变换。它把大数分解问题转化为一个周期查找问题。经典计算机在解决周期查找时依然需要指数时间，而量子计算机可以利用量子傅里叶变换，在多项式时间内完成。
简单来说，Shor 算法的步骤是：
- 随机选一个与 N 互质的数 a。
- 计算函数 f(x) = a^x mod N。这个函数有一个特点：它是周期的。比如，如果周期是 r，那么 a^r ≡ 1 mod N。
- 量子计算机利用叠加态同时计算 f(x) 的所有可能值，然后通过量子傅里叶变换快速找到周期 r。
- 一旦找到周期 r，如果 r 是偶数，就可以用 a^(r/2) ± 1 与 N 求最大公约数，从而分解出 N 的质因数。
关键步骤（寻找周期）在经典计算机上需要指数时间，但在量子计算机上只需要多项式时间。这正是量子霸权所在。
为什么这对 RSA 是毁灭性的
RSA 的安全性直接依赖于大数分解的难度。一旦分解可行，私钥就能从公钥中推导出来。目前安全的 2048 位 RSA，在量子计算机面前就像一把用纸糊的锁。
不仅仅是 RSA，基于椭圆曲线的 ECC、Diffie-Hellman 密钥交换等公钥算法，都会被 Shor 算法的变种攻破。这意味着，整个互联网的信任体系——HTTPS、数字签名、加密货币——都将面临崩塌。
但量子计算机还没来
需要强调的是，目前我们还没有一台足够大的量子计算机能运行 Shor 算法破解实际 RSA。制造稳定的、纠错的、具有数百万量子比特的计算机，还需要很多年。但没有人能确切知道“很多年”是多久。可能是 20 年，也可能是 50 年。量子计算领域的进展正在加速，这让密码学界不得不提前行动起来。
小结
量子计算机之所以能破解 RSA，是因为它利用了量子叠加和纠缠，将指数级的计算问题压缩成多项式级。Shor 算法展示了这种能力的数学基础。虽然今天的量子计算机还很稚嫩，但它们预示着一个新的时代：当量子计算机真正成熟时，我们现有的公钥密码将不再安全。下一节，我们将看到密码学家们如何未雨绸缪，用新的数学难题构建后量子时代的盾牌。