📚 课程目录第1章课程导入与全景概览

1. 课程导入与全景概览

Shor 算法是量子计算发展史上最具标志性的算法之一。它解决的核心问题是：给定一个合数 N，在多项式时间内找出它的非平凡因子。经典计算机上，目前已知最好的通用因数分解算法（数域筛法 GNFS）的复杂度是亚指数级的，对于 2048 位 RSA 模数，经典计算需要的时间远超宇宙年龄；而 Shor 算法把这一问题的量子线路复杂度压到 O((log N)³) 量级，实现了指数级加速。正是这一结果，让"量子计算威胁现有公钥密码体系"从科幻变成了严肃的工程议题。

但需要先建立一个关键认知：Shor 算法并不是"直接分解"的算法，它的主体其实是量子周期求解。整个算法可以拆成"经典归约 + 量子求周期 + 经典后处理"三段。理解这条主线，是学好本课程的前提。

一、从因数分解到周期求解的归约

Shor 的核心技巧是：把"分解 N"转化为"求某个模幂函数的周期"。具体做法是：

随机选取一个整数 a，满足 1 < a < N，且 gcd(a, N) = 1。若 gcd 不为 1，则已经直接得到因子，无需量子计算。
定义函数 f(x) = a^x mod N。这个函数一定是周期的，设其最小正周期为 r，即 a^x+r ≡ a^x (mod N)。
用量子线路求出周期 r。
若 r 为偶数，且 a^r/2 ≢ −1 (mod N)，则 gcd(a^r/2 − 1, N) 与 gcd(a^r/2 + 1, N) 中至少有一个给出非平凡因子。

举一个可手算的示例：取 N = 15，a = 7。计算模幂序列：7¹ mod 15 = 7，7² mod 15 = 4，7³ mod 15 = 13，7⁴ mod 15 = 1，7⁵ mod 15 = 7……可见周期 r = 4。因为 r 为偶数，计算 7² mod 15 = 4，于是 gcd(4−1, 15) = gcd(3, 15) = 3，gcd(4+1, 15) = gcd(5, 15) = 5，得到 15 = 3 × 5。这个例子说明：量子部分只需要输出 r，剩下的因子提取完全由经典计算完成。

二、量子部分为什么能求周期

量子求周期的本质是相位估计。构造一个酉算子 U|y⟩ = |a·y mod N⟩，它的本征值是 e^2πis/r。通过量子相位估计（QPE），把本征值中的 s/r 提取到计数寄存器，再对测量结果做连分数展开，就能还原出 r。因此，Shor 算法的量子线路可以看作"模幂运算 + 逆量子傅里叶变换 + 测量"的组合，其中模幂运算是资源开销最大的部分。

三、整体学习路线图

本课程将沿着"数学基础 → 量子子程序 → 完整算法 → 工程实现 → 影响与前沿"的顺序展开。下图给出各模块之间的依赖关系与数据流：

图中三条纵向主线分别对应"数学—量子—经典"三条知识链，它们在第三层汇聚成完整的 Shor 算法，再向下延伸到工程实现与安全影响。学习时建议按层推进：先补齐模运算与连分数的数学直觉，再理解 QFT 与相位估计的量子机制，最后把模幂运算的线路细节和资源开销吃透。

四、本课程要建立的核心能力

学完本课程后，你应当能够：

独立完成"给定 N 和 a，手算小规模周期 r 并提取因子"的完整推演；
说清 QPE 为什么能提取 s/r，以及连分数如何从测量结果还原 r；
用 Qiskit 搭建 N = 15 的 Shor 线路并解释每个寄存器的角色；
估算分解 2048 位 RSA 模数所需的逻辑量子比特数与 T 门数量级；
理解 Shor 算法对 RSA、ECC 的威胁模型，以及后量子密码（PQC）的应对思路。

学习提示：Shor 算法的难点不在"量子"二字，而在"归约"二字。只要把"分解 → 求周期 → 提取因子"这条经典归约链理解透彻，量子部分就只是实现周期求解的一个工具。建议每学完一个量子子程序，都回到 N = 15、a = 7 这个最小例子上验证一遍。

常见误区：不少初学者以为 Shor 算法能"一次性输出两个因子"。实际上，量子测量给出的是 s/r 的近似值，需要经典连分数后处理才能得到 r；而且当 r 为奇数或 a^r/2 ≡ −1 (mod N) 时，本轮失败，必须换一个 a 重新运行。算法的成功是概率性的，通常重复几次即可。

接下来的章节将从模运算与欧拉定理讲起，逐步搭建起完整的知识体系。请先记住这张全景图：左边是数学，中间是量子，右边是经典后处理，三者缺一不可。