Shor：周期查找与 RSA 的黄昏

RSA 的安全性押在一句话上：分解一个大整数很难。Shor 算法 在 1994 年把这句话拆成两半：一半是经典数论，一半是周期查找。量子机器只加速后一半，但这一半足够致命。

分解只是外壳

取一个与 $N$ 互素的底 $a$，看模幂序列 $a^0, a^1, a^2, \dots$（模 $N$）。它一定会重复，最小的正周期叫 $r$。如果 $r$ 是偶数，且 $a^{r/2}\not\equiv -1 \pmod N$，那么 $\gcd(a^{r/2}-1,N)$ 与 $\gcd(a^{r/2}+1,N)$ 就是 $N$ 的两个非平凡因子。

拿 $N=15$、$a=2$ 试：序列是 1, 2, 4, 8, 1, …，周期 $r=4$。$2^2=4$，$\gcd(3,15)=3$，$\gcd(5,15)=5$，分解完成。

所以 Shor 的量子部分根本不「分解」，它只负责找 $r$；找到之后，剩下的活由经典计算机干。

周期为什么能撬动 RSA

构造算符 $U|y\rangle=|ay \bmod N\rangle$，它的本征相位与 $r$ 挂钩。用 相位估计（核心是 QFT）把周期翻成频率；测到频率，用连分数还原 $r$。量子机器不必把整条序列写下来，这是它比经典快的地方。

威胁也在这里：RSA 靠分解，椭圆曲线密码（ECC）靠离散对数，而离散对数同样能归约到周期查找。受影响的是这两类公钥体系，不是所有密码；对称加密和哈希不会被 Shor 直接攻破。

公开的资源估算给出的量级是：分解一个 2048 比特的 RSA 模数，需要数千个 逻辑比特，还要为纠错付出大量物理比特。截至 2026 年公开报道的量级，逻辑比特的演示规模仍远低于所需，差距在几个数量级；这里没有「某年一定被破解」的时间表。

另一条路是 后量子密码：不换机器，换数学难题，用格、编码或哈希构造经典算法，让 Shor 无从下手。NIST 已在 2024 年把首批标准写进 FIPS 203/204/205；迁移的真正麻烦在存量系统和协议，不在算法本身。