量子算法进阶：Shor算法与大数分解

可视化演示

展示Shor算法周期查找与因子提取、量子线路QFT峰值检测及与经典算法复杂度对比，交互探索量子分解的指数加速。

一、算法概述：一把试不完的钥匙

想象一间金库，铁门上嵌着一把双重密码锁：密码是两个 2048 位的大素数 p 和 q 的乘积 N。管理员把 N 贴在门上供所有人查验，却把 p、q 锁进保险柜。只要有谁能把 N 拆回 p 和 q，整扇门就对他敞开。绝大多数公钥密码系统——尤其是我们每天都在用的 RSA——就是建立在这个门槛上：拆开它，数学上“极难”；不拆开它，一切安然无恙。

经典计算机挑战这道门的姿势很笨拙：拿 2 去试除，不行；拿 3、5、7……一把把钥匙试下去。对小 N 这不成问题，可当 N 有几百位十进制数字时，宇宙诞生至今的时间都不够试。目前最快的经典算法——数域筛法——也只需要亚指数时间，依然令人绝望。正是这道“拆不开的锁”，让 RSA 安安稳稳统治了互联网四十余年。

Shor 算法的革命性在于：它干脆不试钥匙了。它把“两个素数相乘的大数”这个静态对象，变成一个会“踩节拍”的动态过程——选择随机底数 a，观察序列 a^x mod N 的循环规律。锁不再是锁，而是一支等待被听出节奏的舞。这就是本节的第一个核心公式：锁的结构本身。

$$\displaystyle N = p \times q$$

1. 公开的大整数 N：$N$ 是门上的公开锁体，即 RSA 的模数，常见规模是 1024～2048 比特，任何人都能读取和验证。

$$N$$

2. 秘密素数 p：$p$ 是构成锁的两个密码之一，由密钥生成器随机挑选的大素数，绝不公开。

$$p$$

3. 秘密素数 q：$q$ 是与 $p$ 不同的另一个大素数，同样保密；两者共同撑起整把锁。

$$q$$

4. 乘法乘积：$\times$ 表示两个素数相乘得到 $N$；乘法只需一瞬，但从 $N$ 反推 $p$、$q$ 却极其困难——这种不对称正是 RSA 的地基。

$$N = p \times q$$

小结一下：经典方法像一把把试钥匙，指数级的绝望写在复杂度里；而 Shor 的第一步只是重述了锁的结构。真正的魔法在后面——把拆锁换成找节拍。

二、数学原理：把拆锁变成找节拍

小 Q 不再盯着锁孔，而是请舞者们在舞台上踩出一串脚印。她随便挑了一个舞步 a，让舞者依次跳 a 的 1 次方、2 次方、3 次方……每跳一步，就把结果除以 N 取余数，记下一个“脚印值”。奇妙的事情发生了：这些脚印值不是杂乱无章的，而是像音乐的小节一样循环往复。比如 N=15、a=7 时，脚印是 1, 7, 4, 13, 1, 7, 4, 13……正好 4 步一个循环。这个循环长度 r 在数论里叫“a 关于 N 的阶”（order）。

为什么循环会出现？因为在“模 N”的时钟世界里，数字只有 N 个位置：0 到 N-1。走完一圈后，余数必然重复，而且由于底数 a 与 N 互质，序列会严谨地周期循环。找出这个周期 r，就是 Shor 算法全部工作的靶心。而一旦拿到 r，打开金库就只剩最后一步数学手续：如果 r 是偶数，令 x = a^(r/2) mod N，那么 x² ≡ 1 (mod N)，说明 (x-1)(x+1) 能被 N 整除——用欧几里得算法求最大公约数，就能从 x-1 和 x+1 里揪出 p 和 q。

$$\displaystyle a^{r} \equiv 1 \pmod{N}$$

1. 随机底数 a：$a$ 是随机选取的整数，范围在 $2 \le a \le N-2$ 之间，相当于小 Q 随机挑一个舞步。

$$a$$

2. 同余符号：$\equiv \pmod{N}$ 表示左右两边除以 N 的余数相同，是在“模 N 时钟”世界里比较大小。

$$\pmod{N}$$

3. 最小正整数 r：$r$ 是使 $a^r$ 模 N 余 1 的最小正整数，也就是脚印序列完成一次循环所需的步数。

$$a^{r} \equiv 1$$

4. 因子提取：若 r 为偶数且 $a^{r/2} \not\equiv -1 \pmod{N}$，则 $x-1$ 与 $x+1$ 分别与 N 有非平凡公约数，用 gcd 即可拆分：

$$\gcd(a^{r/2} - 1, N), \quad \gcd(a^{r/2} + 1, N)$$

数学这一步很关键：它把“分解大数”等价转化成了“求一个序列的周期”。前者听起来无从下手，后者却长着一副可以被量子计算机“听出来”的模样。去舞团找节拍，总比在宇宙里捞针有希望得多。

三、量子傅里叶变换：全声部同时入耳

舞池里几百位舞者同时踩着不同舞步，耳朵里塞满杂乱的声音，怎么才能听出其中隐藏的主节奏？小 Q 请来一位天才指挥家——量子傅里叶变换（QFT）。这位指挥家的本事是：无论多少声部同时演奏，他都能在脑海中把所有声部按“频率”重新排列，让隐藏的主旋律变成一根根明显的尖峰旗标。周期性越强的信号，尖峰就越突出。

在数学上，量子傅里叶变换就是把一个叠加态从“位置表示”变到“频率表示”。经典傅里叶变换处理一串数字，QFT 处理的是量子态上的概率幅。它把一个均匀叠加的量子态 |x⟩ 变成一系列带相位旋转的叠加，等价于在复平面上“拨动”每个分量的指针。当被分析的函数具有周期 r 时，变换后的输出会在某些特定频率上出现强烈的干涉峰，其他频率则被相消抹平。

这就是 Shor 算法加速的灵魂：经典找周期需要对每个 x 逐个观察、统计，而 QFT 一次性把所有 x 的周期信息汇聚到少数频率峰上。虽然测量只能读出一个结果，但峰的位置携带了周期信息，多测几次就能锁定 r。

$$\displaystyle \hat{f}(k) = \frac{1}{\sqrt{M}} \sum_{x=0}^{M-1} f(x)\, e^{2\pi i k x / M}$$

1. 求和遍历：$\sum_{x=0}^{M-1}$ 遍历所有量子态 x，相当于指挥同时听取所有舞者的声部。

$$\textstyle\sum_{x=0}^{M-1}$$

2. 序列取值：$f(x)$ 是被分析的函数值，在这里就是脚印序列 $a^x \bmod N$。

$$f(x) = a^{x} \bmod N$$

3. 相位旋转：$e^{2\pi i k x / M}$ 是在复平面上按 $kx/M$ 比例旋转的相位因子，让同周期分量的指针对齐、异周期分量互相抵消。

$$e^{2\pi i k x / M}$$

4. 归一化系数：$\frac{1}{\sqrt{M}}$ 保证变换前后总概率保持为 1，是量子力学“概率守恒”的要求。

$$\frac{1}{\sqrt{M}}$$

可以说，QFT 就是这台“节拍分析仪”的核心芯片：它不制造周期，而是把藏在叠加态里的周期“照亮”。没有它，量子叠加只是一堆乱码；有了它，乱码中立刻浮现出规律。

四、周期查找：所有舞者同时踩点

现在轮到大戏上演。小 Q 把舞者们分成两排：第一排每人头上顶一个号码 x（从 0 到 M-1），第二排每个人跟随第一排联动地踩出对应的脚印值 a^x mod N。她先对第一排所有舞者施加“哈达玛门”，让每一个人同时处于所有号码的叠加态；接着执行一个精心编排的“模幂运算”电路，让第二排每个舞者自动算出与第一排号码配对的脚印。一瞬间，整个舞团进入了一种奇妙的纠缠状态：所有 (x, a^x mod N) 配对同时存在。

这就是量子并行。但别高兴太早——如果此刻直接测量第二排，只会坍缩出某一个脚印值，周期信息完全消失。小 Q 的妙招是：先让第一排经过量子傅里叶变换，把所有配对的相位“对齐到周期上”，然后再测量。此时第一排的输出 y 大概率落在 M/r 的整数倍附近，周期 r 的信息以“频率”的形式被保留了下来。

最后一步是经典后处理：把测得的结果 y 除以 M，得到比值 y/M，再用连分数展开逼近一个真分数 c/r，分母就是我们要找的 r。因为量子测量有随机性，单次结果未必完美，所以整个流程通常要重复几次，取最可靠的 r。

$$\displaystyle \left|\psi\right\rangle = \frac{1}{\sqrt{M}} \sum_{x=0}^{M-1} \left|x\right\rangle \otimes \left|a^{x} \bmod N\right\rangle$$

1. 第一寄存器：$\left|x\right\rangle$ 保存号码 x 的叠加态，相当于所有舞者同时顶起所有号码牌。

$$\left|x\right\rangle$$

2. 张量积耦合：$\otimes$ 把两个寄存器耦合成整体态，使第一排和第二排形成一一对应的纠缠关系。

$$\otimes$$

3. 第二寄存器：$\left|a^{x} \bmod N\right\rangle$ 是联动算出的脚印值，与第一排号码配对绑定。

$$\left|a^{x} \bmod N\right\rangle$$

4. 测量与连分数：QFT 后测量第一排得 y，满足 $y/M \approx c/r$，再用连分数展开分母得到周期 r：

$$\frac{y}{M} \approx \frac{c}{r}$$

整个周期查找像一场精心排练的群舞：叠加是全员站位，纠缠是两排联动，QFT 是统一节拍，测量是按下快门，连分数则是冲洗照片。至此，最难啃的骨头已经啃完——剩下的只是把 r 变成 p、q 的收尾工作。

五、量子电路实现：给舞团排练

理论再漂亮，最终要落到硬件上：怎么用真实的量子门把这场“群舞”排练出来？小 Q 的编舞手册里主要有三样工具。第一样是哈达玛门 H，它把一个量子比特从确定态变成叠加态，相当于给舞者发出“同时站到所有位置”的指令。第二样是受控模幂电路 U_a，它实现让第二排舞者联动踩出 a^x mod N 的操作——这是整个线路里最庞大、最耗资源的部分，由一系列受控乘法和模约减器构成。

第三样是逆量子傅里叶变换 QFT⁻¹。读者可能会疑惑：刚才说 QFT 是节拍分析仪，怎么又来个逆变换？其实 Shor 算法里的 QFT 都跟在模幂运算之后，把纠缠态里的相位信息“解码”成可测量的频率峰，正是“正着用”；而在量子相位估计等变体中出现的往往是逆 QFT。无论正逆，本质都是同一台分析仪的校准旋钮。

$$\displaystyle U_{a} \left|x\right\rangle = \left|a x \bmod N\right\rangle$$

1. 酉算子 U_a：$U_a$ 对应模乘法的量子门电路，是可逆的酉变换，保证量子演化不损失信息。

$$U_{a}$$

2. 输入态：$\left|x\right\rangle$ 是寄存器当前状态，代表舞者头顶的号码牌。

$$\left|x\right\rangle$$

3. 输出态：$\left|a x \bmod N\right\rangle$ 是模乘运算的写入结果，所有 x 在叠加中并行完成这一步。

$$\left|a x \bmod N\right\rangle$$

4. 可逆性保证：对 N 取模且 a 与 N 互质时，乘 a 是可逆操作（乘 a 的逆元即可还原），这是量子电路合法性的前提。

$$\left|a^{-1} y \bmod N\right\rangle$$

真实的量子硬件远比编舞手册残酷：每一个量子门都有错误率，叠加态会在几十微秒内“退相干”崩塌，噪声像排练时的起哄声。因此 Shor 电路必须配合量子纠错码，把逻辑比特用多个物理比特冗余编码。这也是为什么理论上 2048 位 RSA 只需几千个逻辑量子比特，实际却需要上百万个物理量子比特——舞团还在排练，离正式登台还远。

六、复杂度分析：速度之争

如果给两位锁匠计时，差距会让人咋舌。经典锁匠用的是数域筛法，完成一次分解所需的基本运算量大约是 e 的“位数的三次根次方”次方——这是一个超多项式甚至亚指数的函数。位数从 1024 加到 2048，耗时不是翻倍，而是平方级地暴增。这也是密码学界敢把 RSA 密钥越设越长的底气：加长密钥就是对暴力最有效的防御。

而量子锁匠小 Q 的账本完全不同。Shor 算法总共需要大约 O((log N)² · loglogN · logloglogN) 个量子门，简化地看就是位数的多项式量级。位数从 1024 涨到 2048，工作量只涨大约 8 倍——对一台还算像样的量子计算机来说，几乎是“加个班”的事。这就是所谓“指数级加速”的真正含义：不是快十倍百倍，而是把复杂度从指数拉回多项式，从“不可能”拉回“可行”。

$$\displaystyle T_{\text{Shor}} = O\left((\log N)^{3}\right)$$

1. 大 O 记号：$O(\cdot)$ 表示算法随输入规模增长时的渐近复杂度，忽略常数只留量级。

$$O(\cdot)$$

2. 对数规模：$\log N$ 是 N 的比特数，例如 RSA-2048 的 $\log N \approx 2048$。

$$\log N$$

3. 立方量级：$(\log N)^3$ 表示量子门数量随比特数立方增长，属于“轻松搞定”的多项式时间。

$$(\log N)^{3}$$

4. 对比经典：经典数域筛法约为 $O\left(e^{(\log N)^{1/3}}\right)$ 次运算，位数翻倍即指数爆炸。

$$O\left(e^{(\log N)^{1/3}}\right)$$

这场速度之争的结论简单而震撼：密钥越长，Shor 的优势越大。对经典是灾难的 2048 位，对量子只是换了个更大的排练厅。密码学家们终于意识到，在多项式时间面前，加长 RSA 密钥只是把死刑缓期执行，而不是赦免。

七、应用与挑战：破锁之后的世界

既然 Shor 算法终将打开 RSA 这把锁，世界该如何应对？我们先看“破锁”的完整落地：拿到周期 r 后，经典后处理用欧几里得算法求两个最大公约数，它们恰好就是 p 和 q。整个过程环环相扣：随机选底数、量子找周期、经典提因子。这既是 Shor 算法的终点，也是量子安全时代的起点。

第一个直接冲击是 RSA 与 ECC 体系的末日倒计时。TLS 握手、数字签名、HTTPS 证书——所有依赖“大数分解难”和“离散对数难”的协议都可能被批量解密。更可怕的是“先截获、后破解”攻击：攻击者今天录下加密流量，等量子计算机成熟后再解密。因此各国政府和云厂商已经开始向“后量子密码”迁移：基于格问题的 LWE（带误差学习）等方案被认为是抗量子的，因为它们连量子计算机也找不到多项式解法。

$$\displaystyle T_{\text{Shor}} = O(b^{3}), \quad b = \lceil \log_{2} N \rceil$$

1. 比特长度 b：$b = \lceil \log_{2} N \rceil$ 是大整数 N 的二进制位数，例如 RSA-2048 的 $b = 2048$。

$$b = \lceil \log_{2} N \rceil$$

2. 量子运行时间：$T_{\text{Shor}}$ 是量子算法完成分解所需的量子门总数，是判断可行性的标尺。

$$T_{\text{Shor}}$$

3. 立方增长：$O(b^{3})$ 表明耗时随位数三次方增长，2048 位只是 $2048^3 \approx 8.6 \times 10^9$ 量级的门。

$$O(b^{3})$$

4. 经典对比：经典分解最快也要亚指数时间，位数翻倍就指数爆炸，因此“加长密钥”救不了 RSA。

$$O\left(e^{b^{1/3}}\right)$$

至于实验进展，目前量子计算机在真实硬件上只分解过 15、21 这类“玩具数字”——2019 年 IBM 用 4 个超导量子比特分解了 15，2023 年有团队用光子平台做到分解 21。真正的瓶颈不在算法设计，而在量子纠错：把错误率压到阈值以下、把逻辑量子比特扩展到数千个，还需要多年工程攻关。舞团的谱子已经写好，但舞台和演员还在建造。好消息是，算法已经为密码学划定了明确的日落时间，后量子世界的帷幕正在拉开。

AI 应用场景

Python 演示

import random  def gcd(a, b):    while b:        a, b = b, a % b    return a  def mod_exp(base, exp, mod):    result = 1    base = base % mod    while exp > 0:        if exp % 2 == 1:            result = (result * base) % mod        exp = exp // 2        base = (base * base) % mod    return result  def find_order(a, N):    r = 1    value = a % N    while value != 1:        value = (value * a) % N        r += 1        if r > N:            return None    return r  def shor_factor(N, attempts=10):    if N % 2 == 0:        return 2    for _ in range(attempts):        a = random.randint(2, N - 2)        common = gcd(a, N)        if common > 1:            return common        r = find_order(a, N)        if r is None or r % 2 != 0:            continue        x = mod_exp(a, r // 2, N)        if x == N - 1:            continue        p = gcd(x - 1, N)        if p > 1:            return p    return None  def factorize(N):    p = shor_factor(N)    if p is None:        print("factorization failed")        return    print("{} = {} x {}".format(N, p, N // p))  if __name__ == "__main__":    for num in [15, 21, 35, 143]:        factorize(num)

1. result = (result * base) % mod快速幂核心：平方再取模，避免大数爆炸
2. while value != 1:逐个累乘找“阶”，模拟量子周期查找的输出
3. r = find_order(a, N)找到周期 r，对应量子部分要“听”出的节拍
4. x = mod_exp(a, r // 2, N)计算半阶值 x，为 gcd 做准备
5. p = gcd(x - 1, N)经典后处理：用欧几里得算法提取非平凡因子

常见误区

面试题