1. 课程导入与问题定义

整数分解问题看起来朴素：给定一个合数 N，找出它的非平凡因子。对 N = 15 这样的数，口算即可得到 3 和 5；但当 N 达到 2048 位时，经典计算机上已知最好的通用算法——数域筛法（GNFS）——所需时间随位数呈亚指数增长，实际代价已远超可行范围。RSA 公钥体系的安全性正是建立在这一代价差距之上：公开模数 N = p·q，只要分解不出 p、q，私钥就无法还原。

1994 年，Peter Shor 给出了多项式时间的量子分解算法，把“分解 N”归约为“求某个模 N 函数的周期”。这一归约本身是纯经典的，量子部分只负责高效找到周期。理解这条分界线，是本课程的第一要务：Shor 算法不是一台“直接吐出因子”的黑箱，而是一条由经典预处理、量子周期查找、经典后处理三段组成的流水线，任何一段出错，最终因子都会错。

问题如何被转化：从分解到求阶

核心思路是：若能找到整数 a（1 < a < N，且 gcd(a, N) = 1）在模 N 乘法下的阶 r，即满足 a^r ≡ 1 (mod N) 的最小正整数，则当 r 为偶数且 a^r/2 ≢ −1 (mod N) 时，有

gcd(a^r/2 − 1, N) 与 gcd(a^r/2 + 1, N)

给出 N 的非平凡因子。以 N = 15、a = 2 为例：2¹=2，2²=4，2³=8，2⁴=16≡1 (mod 15)，故 r = 4。于是 2² = 4，gcd(4−1, 15) = gcd(3, 15) = 3，gcd(4+1, 15) = gcd(5, 15) = 5，一次成功得到 3 和 5。这个手算例子说明：量子计算机要做的，仅仅是“找 r”这一步；其余步骤在经典计算机上完成，且必须做对。

但求阶并不总是顺利。若 a 选得不合适（如 N = 15 时取 a = 4，阶为 2，a¹ = 4 ≡ −11，仍可用；而取 a = 14 时 a ≡ −1，阶为 2 且 a¹ ≡ −1，失败），或 r 为奇数，则需换一个 a 重试。因此完整算法是一个带重试循环的流程，而非一次线性执行。下面的图示把这条流水线的三段结构、判断分支与失败回退关系画在一起，便于在动手实现前建立全局地图。

本课程的双重任务：实现与验证

课程标题中的“实现与验证”不是修辞，而是两条必须同时推进的主线。实现指把上述流水线真正写成可运行的程序：经典部分包括模幂、gcd、连分数展开、候选阶筛选；量子部分包括模乘置换的构造、相位估计线路的搭建与测量结果的读出。验证指对每一段给出可判定的正确性依据：经典函数用已知答案的测试向量比对，量子求阶用模拟器在小规模 N 上核对输出分布，端到端则用一组已知分解结果的合数检查因子乘积是否等于 N、是否非平凡。

之所以强调验证，是因为 Shor 算法的失败模式很隐蔽：相位估计得到的是近似频率，连分数展开可能给出 r 的倍数或约数；测量比特数不足会导致候选阶错误；后处理中 a^r/2 ≡ −1 的情形必须被识别为失败而非“算出因子”。如果只跑一次看到输出就宣布成功，很容易把偶然命中的 gcd 当成算法正确性的证据。因此本课程会在每个阶段设置检查点，并明确“什么样的输出算通过”。

学习路径与先修边界

整体学习路径按“问题—数学—线路—代码—验证”推进：先建立分解与求阶的等价关系，再复习模运算、阶、连分数与量子相位估计的必要结论，随后进入模乘置换与相位估计线路的具体构造，最后落到代码实现与测试。对先修知识的要求是：能读懂模运算与最大公约数、了解复数与单位根、知道量子比特与测量的基本含义；量子傅里叶变换与相位估计会在课程中按“够用即可”的深度展开，不要求预先精通。