Shor算法

Shor 算法（1994）在量子计算机上多项式时间内求解大数分解与离散对数问题，把二者的"经典难解"变成"量子易解"，直接威胁 RSA、ECC 等公钥密码，是后量子密码研究的直接动因。

核心思想：把分解化归为求阶

1. 随机取 $1<a<N$，若 $\gcd(a,N)>1$ 已得因子，否则继续
2. 求 $a$ 模 $N$ 的阶 $r$：使 $a^r\equiv1\pmod N$ 的最小正整数
3. 若 $r$ 为偶数且 $a^{r/2}\not\equiv\pm1\pmod N$，则 $\gcd(a^{r/2}-1,N)$ 与 $\gcd(a^{r/2}+1,N)$ 均为非平凡因子；否则换 $a$ 重试

量子求阶

阶的求解用量子相位估计完成：制备叠加态 $\sum_x|x\rangle$，应用模幂 $|x\rangle\mapsto|x\rangle|a^x\bmod N\rangle$，对第一寄存器做量子傅里叶变换后测量，由测得值的高精度逼近得到 $k/r$（$k$ 随机），再经连分数展开恢复 $r$。其中的模幂运算用快速幂的量子版本实现。

复杂度与成功率

• 整体时间 $O((\log N)^2(\log\log N)(\log\log\log N))$，空间 $O(\log N)$
• 对随机 $a$，$r$ 为偶数且 $a^{r/2}\not\equiv\pm1$ 的概率至少 $1/2$，重试少数几次即可成功

示例

• $N=15$，$a=2$：$2^4\equiv1\pmod{15}$，$r=4$，$2^2=4\not\equiv\pm1$；$\gcd(3,15)=3$，$\gcd(5,15)=5$ → $15=3\cdot5$
• $N=21$，$a=2$：$2^6\equiv1\pmod{21}$，$r=6$，$2^3=8\not\equiv\pm1$；$\gcd(7,21)=7$，$\gcd(9,21)=3$ → $21=3\cdot7$

影响

经典分解最快的数域筛法是亚指数时间，而 Shor 算法把 RSA 与 Diffie–Hellman 的安全性根基移除，推动格基约化算法等格基密码成为后量子方案的主流候选。