2. 经典数论基础

Shor 算法之所以能把因数分解转化为量子周期求解，前提是它站在一整套经典数论工具之上。理解这些工具，不只是为了看懂公式，更是为了明白：为什么“求周期”能推出“分解因数”，以及量子线路里那些模乘、模幂操作到底在算什么。本节把整除、同余、最大公约数、欧几里得算法、模运算与模逆元串成一条可操作的链条，并用具体数值演示每一步。

整除与同余：把“余数”变成一种结构

设 a、b 为整数且 b≠0。若存在整数 k 使 a = b·k，则称 b 整除 a，记作 b | a，此时 b 是 a 的因数，a 是 b 的倍数。整除关系具有传递性：若 c | b 且 b | a，则 c | a。这条性质在因数分解中反复用到——只要找到一个非平凡因数，就能继续往下拆。

同余是整除的“带余版本”。给定正整数 m（称为模），若 m | (a − b)，则称 a 与 b 对模 m 同余，记作 a ≡ b (mod m)。等价地说，a 和 b 除以 m 得到相同的余数。例如 17 ≡ 2 (mod 5)，因为 17 − 2 = 15 能被 5 整除，两者除以 5 都余 2。同余关系满足自反、对称、传递，并且可以与加、减、乘“交换”：若 a ≡ b、c ≡ d (mod m)，则 a+c ≡ b+d、a−c ≡ b−d、a·c ≡ b·d (mod m)。这条性质是模运算能整体化简的根本原因。

需要注意，同余对除法并不无条件成立。例如 6 ≡ 2 (mod 4)，两边同除以 2 得 3 ≡ 1 (mod 4)，这是错的。除法要成立，必须借助模逆元，这正是后文要解决的问题。

最大公约数与欧几里得算法

两个整数 a、b 的最大公约数 gcd(a, b) 是同时整除二者的最大正整数。当 gcd(a, b) = 1 时称 a 与 b 互素。在 Shor 算法中，第一步就是随机取 a，计算 gcd(a, N)；若结果大于 1，直接得到 N 的一个非平凡因数，算法提前结束；若等于 1，才进入量子周期求解阶段。因此 gcd 不只是数学概念，而是算法的“快速通道”。

求 gcd 的高效方法是欧几里得算法，其核心恒等式是 gcd(a, b) = gcd(b, a mod b)。反复用较小数除较大数取余，直到余数为 0，此时的除数就是最大公约数。以 gcd(48, 18) 为例：

gcd(48, 18)
48 = 2 × 18 + 12   → gcd(18, 12)
18 = 1 × 12 + 6    → gcd(12, 6)
12 = 2 × 6  + 0    → 余数为 0，停止
所以 gcd(48, 18) = 6

该算法的时间复杂度与输入位数成多项式关系（约为 O(log min(a,b)) 次除法），这正是它能被经典计算机高效执行、并被 Shor 算法当作子程序反复调用的原因。与之配套的扩展欧几里得算法还能同时求出满足 ax + by = gcd(a, b) 的整数 x、y，这组系数就是求模逆元的直接工具。

模运算与模逆元

模运算把整数按余数归类。所有与 a 对模 m 同余的整数构成一个同余类，模 m 下共有 m 个同余类，记作 Z_m = {0, 1, …, m−1}。在 Z_m 上可以定义加法与乘法，结果再对 m 取余。例如模 7 下：3 + 6 = 9 ≡ 2，3 × 6 = 18 ≡ 4。这种“先算后取余”与“先取余再算”结果一致，使得大数模幂可以被逐步约简，避免中间结果爆炸。

模逆元是模运算中的“除法”。若存在整数 x 使 a·x ≡ 1 (mod m)，则称 x 是 a 对模 m 的逆元，记作 a⁻¹ mod m。逆元存在的充要条件是 gcd(a, m) = 1。当 m 为素数 p 时，所有 1 ≤ a ≤ p−1 都与 p 互素，因此每个非零元都有逆元，Z_p 构成一个有限域。这一性质在 Shor 算法中非常关键：模幂底数 a 必须与 N 互素，才能保证后续周期结构良好。

求逆元可用扩展欧几里得算法。以求 3 对模 7 的逆元为例，先做欧几里得过程：

7 = 2 × 3 + 1
3 = 3 × 1 + 0
回代：1 = 7 − 2 × 3
即 1 = (−2) × 3 + 1 × 7
所以 3 × (−2) ≡ 1 (mod 7)
取 −2 mod 7 = 5，故 3⁻¹ ≡ 5 (mod 7)
验证：3 × 5 = 15 = 2 × 7 + 1 ≡ 1 (mod 7) ✓

再看一个与因数分解直接相关的例子。设 N = 15，取 a = 2，gcd(2, 15) = 1，满足互素条件。计算 2 的模 15 幂次：2¹=2，2²=4，2³=8，2⁴=16≡1，于是 2 对模 15 的周期为 r = 4。因为 r 是偶数，可计算 a^(r/2) = 2² = 4，再求 gcd(4−1, 15) = gcd(3, 15) = 3，以及 gcd(4+1, 15) = gcd(5, 15) = 5，成功得到 15 = 3 × 5。这个例子完整展示了“互素判断 → 求周期 → 用周期构造因数”的经典逻辑，而量子部分要加速的，正是中间那个“求周期”步骤。

各概念之间的关系

整除定义同余，同余支撑模运算，模运算中的除法依赖模逆元，而模逆元的存在性由最大公约数判定，最大公约数又由欧几里得算法高效求出。这条依赖链可以用下图表示，它也是 Shor 算法经典预处理部分的逻辑骨架。

把这张图记牢，后续看到模幂线路、周期寄存器或连分数后处理时，就能迅速定位每一步在经典数论中的对应位置。下一阶段要做的，是把“求周期”这件事从经典逐次试算，升级为量子并行相位估计。