Shor 算法

Shor 算法（Shor’s Algorithm）由 Peter Shor 于 1994 年提出，是量子计算领域最具里程碑意义的算法之一。它证明了量子计算机能够在多项式时间内完成整数因数分解——而这个问题对经典计算机而言，在大数情况下仍是计算瓶颈，也正是 RSA 加密体系安全性的根基。

问题背景：为什么因数分解很重要

RSA 加密的核心假设是：给定两个大素数 $p,q$，计算 $N=p\times q$ 很容易，但从 $N$ 反推出 $p,q$ 极其困难。目前最好的经典算法（数域筛法，Number Field Sieve）的时间复杂度约为：

$O\left(\exp \left({\left(\frac{64}{9}\right)}^{1/3}(\log N{)}^{1/3}(\log \log N{)}^{2/3}\right)\right)$

这是亚指数级的：它远慢于任何多项式，又远快于指数级的暴力搜索。即便如此，对于 2048 位的 RSA 模数，经典计算机仍需要天文数字般的运算量。

而 Shor 算法的时间复杂度为 $O((\log N{)}^3)$——多项式级，理论上可在数小时内分解 2048 位整数。

Shor 算法的核心思想

Shor 算法将因数分解问题归约为求阶问题（order-finding problem）：给定整数 $N$（待分解）和随机选取的 $a$（$1<a<N$，且 $\gcd (a,N)=1$），求最小正整数 $r$ 使得 $a^r\equiv 1(\mathrm{mod}N)$。这个 $r$ 称为 $a$ 模 $N$ 的阶（multiplicative order）。

一旦求得 $r$：若 $r$ 为偶数且 $a^{r/2}\not\equiv -1(\mathrm{mod}N)$，则 $\gcd (a^{r/2}-1,N)$ 与 $\gcd (a^{r/2}+1,N)$ 立即给出 $N$ 的非平凡因子（引理 1 及其证明见下文）；对随机选取的 $a$，这两个条件以至少 $1/2$ 的概率同时满足（证明见下文”失败概率分析”）。

量子部分的任务就是高效求阶，其结构是”相位估计 + 连分数”：量子傅里叶变换把周期 $r$ 转化为测量值 $j$，使得 $j/2^n$ 是某个分母为 $r$ 的分数 $c/r$ 的近似；再用经典的连分数（continued fraction）展开从这一近似中恢复出 $r$。

算法步骤

第一步：经典预处理

1. 随机选取 $a\in \{2,3,\dots ,N-1\}$
2. 计算 $\gcd (a,N)$，若大于 1 则直接得到因子，算法结束

第二步：量子求阶（核心）

这是量子计算机发挥作用的步骤。构造两个量子寄存器：

• 寄存器 1：$n=\lceil {\log }_2{N}^2\rceil$ 个量子比特，用于存储 $x$ 的叠加态；以下记 $Q=2^n$，注意 $Q\ge N^2$
• 寄存器 2：$\lceil {\log }_{2}N\rceil$ 个量子比特，用于存储 $a^x\mathrm{mod}N$ 的结果

操作流程：

1. 初始化寄存器 1 为等权叠加态：$|\psi ⟩=\frac{1}{\sqrt{Q}}{\sum }_{x=0}^{Q-1}|x⟩$

2. 计算模幂运算 $|x⟩|0⟩\to |x⟩|a^x\mathrm{mod}N⟩$（可用模幂电路高效实现）

3. 对寄存器 2 进行测量，得到某个值 $y=a^{x_0}\mathrm{mod}N$，寄存器 1 坍缩为所有满足 $a^x\equiv y(\mathrm{mod}N)$ 的 $x$ 的等权叠加，即 $x=x_0,x_0+r,x_0+2r,\dots$

4. 对寄存器 1 施加量子傅里叶变换（Quantum Fourier Transform, QFT）：$\text{QFT}:|j⟩\mapsto \frac{1}{\sqrt{Q}}{\sum }_{k=0}^{Q-1}{e}^{2\pi ijk/Q}|k⟩$

5. 测量寄存器 1，以高概率得到接近 $Q/r$ 的整数倍的值 $j$

6. 用连分数展开从测量结果 $j/Q$ 中提取候选分母，并逐一验证 $a^q\mathrm{mod}N$ 是否等于 1，取通过验证的最小候选作为 $r$；若所有候选都失败，重跑本步骤

第三步：经典后处理

1. 若 $r$ 为奇数，回到第一步重新选 $a$
2. 计算 $a^{r/2}\mathrm{mod}N$，若 $\equiv -1(\mathrm{mod}N)$，回到第一步
3. 计算 $\gcd (a^{r/2}-1,N)$ 和 $\gcd (a^{r/2}+1,N)$，得到非平凡因子

理论推导

以下给出算法正确性的完整数学证明。

从周期到因子：为什么求阶能分解 N

引理 1：设 $N$ 为奇合数，$\gcd (a,N)=1$，$r$ 为 $a$ 模 $N$ 的阶。若 $r$ 为偶数且 $a^{r/2}\not\equiv -1(\mathrm{mod}N)$，则 $\gcd (a^{r/2}-1,N)$ 和 $\gcd (a^{r/2}+1,N)$ 都是 $N$ 的非平凡因子（即严格介于 $1$ 与 $N$ 之间）。

证明分四步。

第一步：$N$ 整除两个因子的乘积。由阶的定义 $a^r\equiv 1(\mathrm{mod}N)$，即 $N\mid (a^r-1)$。$r$ 为偶数，故 $r/2$ 是正整数，可对 $a^r-1=(a^{r/2}{)}^2-1$ 用平方差公式：

$a^r-1=(a^{r/2}-1)(a^{r/2}+1)$

因此 $N\mid (a^{r/2}-1)(a^{r/2}+1)$。

第二步：两个因子几乎互素。它们的差为 2，而两个整数的公因数必整除其差，故

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

若 $N$ 为偶数则可直接被 2 整除，无需 Shor 算法，故我们只需考虑奇数 $N$：$N$ 的每个素因子 $p$ 都是奇数，不整除 2，因此 $p$ 不能同时整除 $(a^{r/2}-1)$ 和 $(a^{r/2}+1)$。

第三步：素因子被划分到两侧。考虑 $N$ 的任一素幂因子 $p^e$（$p$ 奇素数）。由第一步 $p^e\mid (a^{r/2}-1)(a^{r/2}+1)$；由第二步 $p$ 只整除其中一个因子，于是 $p^e$ 的全部幂次只能落在同一个因子里。把 $N$ 的所有素幂按此划分，记

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

则 $N=N_{-}\cdot N_{+}$ 且 $\gcd (N_{-},N_{+})=1$。

第四步：两个因子都是非平凡的。$N_{-}=N$ 当且仅当 $N\mid a^{r/2}-1$，即 $a^{r/2}\equiv 1(\mathrm{mod}N)$。这不可能发生：$r$ 是使 $a^k\equiv 1(\mathrm{mod}N)$ 成立的最小正整数，而 $0<r/2<r$，若 $a^{r/2}\equiv 1$ 则与 $r$ 的最小性矛盾。$N_{+}=N$ 当且仅当 $a^{r/2}\equiv -1(\mathrm{mod}N)$，已被引理的条件排除。于是 $N_{-},N_{+}<N$；又由 $N_{-}{N}_{+}=N$ 知两者都不能是 1（若 $N_{-}=1$ 则 $N_{+}=N$，矛盾；$N_{+}$ 同理）。故两者都是 $N$ 的非平凡因子。∎

具体验证（以 $N=15,a=7,r=4$ 为例）：

• $7^2-1=48$，$\gcd (48,15)=3$ ✓
• $7^2+1=50$，$\gcd (50,15)=5$ ✓
• $15$ 的素因子 $\{3,5\}$ 被分别”捕获”

失败概率分析。算法失败有两种情况：$r$ 为奇数，或 $a^{r/2}\equiv -1(\mathrm{mod}N)$。我们以 $N=pq$（两个不同奇素数）为例把两种情况的概率都算出来；更一般的奇合数可用同样的计数方法处理。

预备计数：记 $v_2(m)$ 为整数 $m$ 所含素因子 2 的个数（即 $m=2^{v_2(m)}\times$ 奇数）。设 $p-1=2^{t_p}{u}_p$（$u_p$ 为奇数）。${\mathbb{Z}}_p^{\ast }$ 是 $p-1$ 阶循环群，其中阶整除 $2^s{u}_p$ 的元素恰有 $2^s{u}_p$ 个。因此，$a$ 模 $p$ 的阶 $r_p$ 满足 $v_2(r_p)=s$（$1\le s\le t_p$）的比例为 $\frac{2^s{u}_p-2^{s-1}{u}_p}{2^{t_p}{u}_p}=2^{s-1-t_p}$，$v_2(r_p)=0$（阶为奇数）的比例为 $2^{-t_p}$。由中国剩余定理（Chinese Remainder Theorem, CRT），$a$ 模 $N$ 均匀当且仅当 $a\mathrm{mod}p$ 与 $a\mathrm{mod}q$ 独立均匀；且 $a^k\equiv 1(\mathrm{mod}N)$ 当且仅当模 $p$、模 $q$ 同时为 1，故 $r=\mathrm{lcm}(r_p,r_q)$，其中 $r_p,r_q$ 是 $a$ 模 $p,q$ 的阶。

情况一（$r$ 为奇数）：$r=\mathrm{lcm}(r_p,r_q)$ 为奇数当且仅当 $r_p,r_q$ 都是奇数，概率为

$2^{-t_p}\cdot 2^{-t_q}=2^{-(t_p+t_q)}\le \frac{1}{4}$

情况二（$a^{r/2}\equiv -1(\mathrm{mod}N)$）：设 $r$ 为偶数。$(a^{r/2}{)}^2\equiv 1(\mathrm{mod}p)$，而在域 ${\mathbb{Z}}_p$ 中 $1$ 的平方根只有 $\pm 1$，故 $a^{r/2}\mathrm{mod}p\in \{+1,-1\}$，$\mathrm{mod}q$ 同理。于是签号组合 $(a^{r/2}\mathrm{mod}p,a^{r/2}\mathrm{mod}q)$ 有四种可能：

• $(+,+)$：意味着 $a^{r/2}\equiv 1(\mathrm{mod}N)$，与 $r$ 的最小性矛盾，不可能发生（由 $v_2(r)=\max (v_2(r_p),v_2(r_q))$，至少一侧达到最大值，也可看出 $a^{r/2}$ 不可能模两个素数同时为 $+1$）；
• $(-,-)$：即 $a^{r/2}\equiv -1(\mathrm{mod}N)$，算法失败；
• $(+,-)$ 或 $(-,+)$：此时 $p$ 整除其中一个因子、$q$ 整除另一个，$\gcd (a^{r/2}\pm 1,N)$ 恰为 $\{p,q\}$，算法成功。

$(-,-)$ 何时发生？$a^{r/2}\equiv -1(\mathrm{mod}p)$ 等价于 $r_p\nmid r/2$，即 $v_2(r_p)=v_2(r)$（奇部自动相容，因为 $r_p\mid r$）；模 $q$ 同理。两侧同时为 $-1$ 等价于 $v_2(r_p)=v_2(r_q)=s$ 对某个 $s\ge 1$ 成立，其概率为

${\sum }_{s=1}^m{2}^{s-1-t_p}\cdot 2^{s-1-t_q}=\frac{2^{2m}-1}{3\cdot 2^{t_p+t_q}},m=\min (t_p,t_q)$

（等比数列求和：公比为 4。）

把两种失败情况相加，总失败概率为

$\frac{1}{2^{t_p+t_q}}+\frac{2^{2m}-1}{3\cdot 2^{t_p+t_q}}=\frac{2^{2m}+2}{3\cdot 2^{t_p+t_q}}\le \frac{2^{2m}+2}{3\cdot 2^{2m}}\le \frac{1}{2}$

其中用到 $t_p,t_q\ge m\ge 1$。等号在 $t_p=t_q=1$（即 $p\equiv q\equiv 3(\mathrm{mod}4)$）时取到，此时两种失败各占 $1/4$。结论：单次随机选取 $a$ 的成功概率至少为 $1/2$，重复 $k$ 次后失败概率降至 $1/2^k$。

以 $N=15=3\times 5$ 全量枚举验证（$\gcd (a,15)=1$ 的 $a$ 共 7 个）：

$a$	$r$	$a^{r/2}\mathrm{mod}15$	$(\mathrm{mod}3,\mathrm{mod}5)$	结果
2	4	4	$(+1,-1)$	$\gcd (3,15)=3,\gcd (5,15)=5$ ✓
4	2	4	$(+1,-1)$	$3,5$ ✓
7	4	4	$(+1,-1)$	$3,5$ ✓
8	4	4	$(+1,-1)$	$3,5$ ✓
11	2	11	$(-1,+1)$	$\gcd (10,15)=5,\gcd (12,15)=3$ ✓
13	4	4	$(+1,-1)$	$3,5$ ✓
14	2	14	$(-1,-1)$	失败（$a^{r/2}\equiv -1$）

7 个中有 6 个成功，比例 $\approx 0.857\ge 1/2$，与理论一致。

QFT 提取周期的数学原理

测量寄存器 2 得到 $y$ 后，寄存器 1 坍缩为所有满足 $a^x\equiv y(\mathrm{mod}N)$ 的 $|x⟩$ 的等权叠加态。设最小的解为 $x_0\in \{0,1,\dots ,r-1\}$，则解集为 $\{x_0,x_0+r,x_0+2r,\dots \}$ 中不超过 $Q-1$ 的那些，于是

$|\varphi ⟩=\frac{1}{\sqrt{M}}{\sum }_{k=0}^{M-1}|x_0+kr⟩,M=\lfloor \frac{Q-1-x_0}{r}\rfloor +1\approx \frac{Q}{r}$

（项数 $M$ 的由来：要求 $x_0+kr\le Q-1$，即 $k\le (Q-1-x_0)/r$，故 $k$ 的最大值为 $\lfloor (Q-1-x_0)/r\rfloor$，共 $M$ 项。）

对 $|\varphi ⟩$ 施加 QFT。第 $j$ 个分量的振幅为

${\alpha }_j=\frac{1}{\sqrt{Q\cdot M}}{\sum }_{k=0}^{M-1}{e}^{2\pi ij(x_0+kr)/Q}=\frac{e^{2\pi ij{x}_0/Q}}{\sqrt{QM}}{\sum }_{k=0}^{M-1}{\left[e^{2\pi ijr/Q}\right]}^k$

内层是公比为 $e^{2\pi i\Delta }$（$\Delta =jr/Q$）、共 $M$ 项的几何级数。用等比求和公式并提取公因子的相位，可得其模长为

$\left|{\sum }_{k=0}^{M-1}{e}^{2\pi ik\Delta }\right|=\left|\frac{\sin (\pi M\Delta )}{\sin (\pi \Delta )}\right|$

当 $\Delta$ 接近整数时各项几乎同相，级数模长接近 $M$，发生相长干涉；当 $\Delta$ 接近半整数时各项几乎两两反相，级数模长接近 0，发生相消干涉。定量地，利用不等式 $\sin t\ge \frac{2}{\pi }t$（$0\le t\le \pi /2$）与 $|\sin t|\le |t|$：当 $|\Delta |\le \frac{1}{2M}$ 时，

$\left|\frac{\sin (\pi M\Delta )}{\sin (\pi \Delta )}\right|\ge \frac{2M|\Delta |}{\pi |\Delta |}=\frac{2M}{\pi }$

即模长至少是最大值的 $2/\pi \approx 0.64$ 倍。

现在确定峰的位置。对每个 $c\in \{0,1,\dots ,r-1\}$，取 $j_c$ 为最接近 $\frac{cQ}{r}$ 的整数，则 $\left|j_c-\frac{cQ}{r}\right|\le \frac{1}{2}$，于是

$|\Delta |=\frac{r}{Q}\left|j_c-\frac{cQ}{r}\right|\le \frac{r}{2Q}\lesssim \frac{1}{2M}$

（最后一步是因为 $M\approx Q/r$；由于 $Q\ge N^2\gg r$，边界效应可忽略。）因此峰处的振幅满足 $|{\alpha }_{j_c}|\gtrsim \frac{2}{\pi }\sqrt{\frac{M}{Q}}$，测量概率

$P(j_c)\gtrsim \frac{4}{{\pi }^2}\cdot \frac{M}{Q}\approx \frac{4}{{\pi }^2}\cdot \frac{1}{r}$

$r$ 个峰合计的总概率约为 $4/{\pi }^2\approx 0.40$，这就是单次量子运行”落在好峰上”的概率下限。

关键在于峰的位置编码了 $r$：由 $\left|j_c-\frac{cQ}{r}\right|\le \frac{1}{2}$ 两边除以 $Q$ 得

$\left|\frac{j_c}{Q}-\frac{c}{r}\right|\le \frac{1}{2Q}\le \frac{1}{2N^2}<\frac{1}{2r^2}$

（用到 $Q\ge N^2$ 与 $r<N$：$a$ 的阶整除群阶 $\phi (N)<N$。）换言之，测量值 $j/Q$ 是某个以 $r$ 为分母的有理数 $c/r$ 的近似，且近似精度好到 $1/(2r^2)$ 以内。问题于是转化为：从一个有理数的高精度近似值恢复其分母——这正是连分数的经典用武之地。

连分数算法：从测量值中提取 r

连分数展开（continued fraction）是将有理数表示为嵌套分数的标准工具。对任意正有理数 $x/y$，其连分数展开为：

$\frac{x}{y}=a_0+\frac{1}{a_1+\frac{1}{a_2+\cdots +\frac{1}{a_k}}}$

记作 $[a_0;a_1,a_2,\dots ,a_k]$，其中 $a_i$ 为正整数（$a_0$ 可为 0）。逐级截断得到的分数 $p_t/q_t=[a_0;a_1,\dots ,a_t]$ 称为渐近分数（convergent）。

展开算法是欧几里得辗转相除法的直接改写：$a_0=\lfloor x/y\rfloor$，对余数 $x\mathrm{mod}y$ 与 $y$ 重复同样操作，直到余数为 0。整个过程在 $O((\log N{)}^3)$ 时间内完成。

为什么连分数能恢复 $r$（Legendre 定理）：若分数 $p/q$（既约）满足 $|\alpha -p/q|<\frac{1}{2q^2}$，则 $p/q$ 必为 $\alpha$ 的某个渐近分数。把上一节的结果代入：$j_c/Q$ 与 $c/r$ 的偏差小于 $\frac{1}{2N^2}<\frac{1}{2r^2}$；将 $c/r$ 化为既约分数 $c^{\prime }/r^{\prime }$（$r^{\prime }=r/\gcd (c,r)$ 整除 $r$），偏差进一步小于 $\frac{1}{2r^{\prime 2}}$。于是 $c^{\prime }/r^{\prime }$ 必然出现在 $j_c/Q$ 的渐近分数序列中。

恢复流程：对测量值 $j$ 做连分数展开，列出分母不超过 $N$ 的所有渐近分数分母 $q_t$ 作为候选。由于 $r^{\prime }\mid r$ 且 $a^r\equiv 1(\mathrm{mod}N)$，候选中若有某个 $q$ 使 $a^q\equiv 1(\mathrm{mod}N)$（用快速模幂验证，代价多项式），它就是阶的一个因子。完整的后处理为：

1. 若某候选 $q_t$ 满足 $a^{q_t}\equiv 1(\mathrm{mod}N)$：取其中最小者，它就是 $r$（阶是最小的这样的正指数）；
2. 若候选 $q_t$ 都不满足（这发生在 $\gcd (c,r)>1$、既约分母 $r^{\prime }<r$ 时）：依次尝试 $q_t$ 的 2 倍、3 倍等小倍数并验证，因为 $r=\gcd (c,r)\cdot r^{\prime }$ 是 $r^{\prime }$ 的小倍数；
3. 若仍失败或测得 $j=0$（对应 $c=0$，不含信息）：重跑量子部分。多次运行取候选的最小公倍数也是常用策略。

计算实例（$N=15$，$Q=2^8=256$，$a=7$，$r=4$；此时 $r\mid Q$，四个峰 $j_c=64c$ 均为整数，每个以概率 $M/Q=1/4$ 测得）：

• 测得 $j=192$：做辗转相除 $256=1\times 192+64$，$192=3\times 64+0$，故 $192/256=[0;1,3]$，渐近分数依次为 $0/1,1/1,3/4$。候选分母 $\{1,4\}$ 中验证：$7^1=7\not\equiv 1(\mathrm{mod}15)$，候选 1 不通过；$7^4=2401\equiv 1(\mathrm{mod}15)$ ✓，故 $r=4$，提取成功（此时 $c=3$）。
• 测得 $j=64$：$64/256=[0;4]$，渐近分数为 $0/1,1/4$，同样得到候选 $r=4$，验证通过（此时 $c=1$）。
• 测得 $j=128$：$128/256=[0;2]$，渐近分数为 $0/1,1/2$，候选 $r^{\prime }=2$。但 $7^2=49\equiv 4\not\equiv 1(\mathrm{mod}15)$，验证失败；改试倍数 $2\times 2=4$：$7^4\equiv 1(\mathrm{mod}15)$ ✓，故 $r=4$。（这里 $c=2$ 与 $r=4$ 有公因子 2，既约分母 $2=r/2$，正是上述第 2 种情形。）
• 测得 $j=0$：对应 $c=0$，不含信息，重跑。

量子电路结构

![Shor 算法量子电路](../assets/circuits/s

以 $N=15,a=7$ 为例：把 $x$ 按二进制分解 $x=x_0+2x_1+4x_2+\cdots$，模幂 $a^x$ 就分解为一系列受控模乘，第 $k$ 个受控门在控制比特为 1 时对目标寄存器执行 $|y⟩\mapsto |a^{2^k}y\mathrm{mod}N⟩$。所需的乘数依次为 $7^{2^0}\mathrm{mod}15=7$、$7^{2^1}\mathrm{mod}15=4$、$7^{2^2}\mathrm{mod}15=1$——第三个受控门退化为恒等操作，因为 $r=4$ 整除 $2^2$，$a^{2^2}=a^4\equiv 1$。这正体现了周期结构：一旦指数超过周期，乘数就开始循环。

具体例子：分解 N = 15

1. 随机选 $a=7$，$\gcd (7,15)=1$
2. 量子求阶：
   • $7^1=7$
   • $7^2=49\equiv 4(\mathrm{mod}15)$
   • $7^3=343\equiv 13(\mathrm{mod}15)$
   • $7^4=2401\equiv 1(\mathrm{mod}15)$
   • 故 $r=4$
3. $r$ 为偶数，$7^{4/2}=7^2=49\equiv 4\not\equiv -1(\mathrm{mod}15)$
4. 计算 $\gcd (4-1,15)=\gcd (3,15)=3$
5. 计算 $\gcd (4+1,15)=\gcd (5,15)=5$
6. 得到：$15=3\times 5$

复杂度分析

步骤	复杂度
模幂运算（量子）	$O((\log N{)}^3)$ 量子门
量子傅里叶变换	$O((\log N{)}^2)$ 量子门
经典连分数展开	$O((\log N{)}^3)$
总体	$\mathbf{O}((\log \mathbf{N}{)}^3)$

对比经典最优算法的亚指数复杂度，这是指数级加速。

当前进展与局限

已实现的里程碑：

• 2001 年，IBM 在 7 量子比特的量子计算机上用 Shor 算法分解了 15
• 2019 年，Google 实现了 53 量子比特的量子优越性（Sycamore）
• 2023 年起，各类量子纠错码取得实质性进展

现实挑战：

• 分解 2048 位 RSA 需要约 4000 个逻辑量子比特，考虑纠错开销需要数百万个物理量子比特
• 当前最先进的量子处理器约 1000+ 物理量子比特
• 量子退相干和门错误率仍是核心瓶颈

对密码学的影响

虽然量子计算机短期内还无法运行实用规模的 Shor 算法，但威胁已经推动了后量子密码学（Post-Quantum Cryptography）的发展：

• NIST 已于 2024 年标准化首批后量子算法（ML-KEM、ML-DSA 等）
• “现在截获、未来解密”（Harvest Now, Decrypt Later）是现实威胁
• 从 RSA/ECC 迁移到后量子算法需要数年至数十年的过渡期

总结

Shor 算法展示了量子计算在特定问题上相对于经典计算的指数级优势。它的推导链条环环相扣：因数分解归约为求阶；求阶归约为”用 QFT 测出 $c/r$ 的近似 $j/Q$“；连分数定理保证能从近似值恢复分母；平方差分解与最大性论证保证阶能还原出因子。理解它不仅有助于把握量子计算的本质——利用量子叠加与干涉实现并行计算——也让我们认识到量子时代对现代密码体系的深远影响。

---

参考文献：

1. Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. FOCS 1994.
2. Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information. Cambridge University Press.
3. NIST (2024). Post-Quantum Cryptography Standardization. https://csrc.nist.gov/projects/post-quantum-cryptography

---

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch04-classic-algorithms/shors-algorithm-tutorial
• 内容遵循 CC BY-NC-SA 4.0 许可协议