2. 数学基础回顾

Shor 算法之所以能在多项式时间内完成因数分解，关键并不在于量子傅里叶变换本身有多“神奇”，而在于它把“找因子”这个数论问题巧妙地转化成了“求周期”问题。而支撑这一转化的，正是模运算、最大公约数、欧拉定理与乘法阶这四个基础工具。本节不追求数论体系的完整铺陈，而是围绕 Shor 算法真正会用到的部分，把定义、性质与计算方式讲清楚，并说明它们在算法流程中各自扮演什么角色。

一、模运算：把无限整数折叠进有限环

模运算的核心是“同余”。给定正整数 N，若两个整数 a、b 满足 N 整除 (a−b)，就称 a 与 b 对模 N 同余，记作 a ≡ b (mod N)。直观理解，就是把整数按除以 N 的余数分成 N 个等价类，所有运算都在这 N 个“格子”里进行。对 Shor 算法而言，我们关心的对象是模 N 的乘法群，即所有与 N 互素的剩余类构成的集合，记作 (Z/NZ)*。

模运算有三条在实现中必须牢记的性质：其一，加法、减法、乘法都可以先取模再运算，结果不变，这使得大数运算可以被有效控制；其二，除法不能随意进行，只有当除数与 N 互素时才存在模逆元；其三，模幂运算 a^x mod N 可以用“平方—乘”方法在 O(log x) 次模乘内完成，这是经典计算机模拟 Shor 算法时最频繁的操作。举一个具体例子：取 N = 15，a = 7，计算 7⁴ mod 15。先算 7² = 49 ≡ 4 (mod 15)，再算 7⁴ ≡ 4² = 16 ≡ 1 (mod 15)。这个“回到 1”的现象，正是下一节乘法阶的雏形。

二、最大公约数：筛选可用的底数

最大公约数 gcd(a, N) 是 Shor 算法流程中的第一道“筛子”。算法开始时随机选取一个底数 a（1 < a < N），先计算 gcd(a, N)。若结果大于 1，说明已经直接找到了 N 的一个非平凡因子，算法提前结束——这是幸运情形，概率不高但确实存在。若 gcd(a, N) = 1，说明 a 与 N 互素，a 属于乘法群 (Z/NZ)*，才具备良好的乘法阶，才能进入量子求周期的主流程。

计算 gcd 的标准工具是欧几里得算法：反复用较小数去除较大数取余，直到余数为零，最后一个非零余数即为 gcd。例如 gcd(7, 15)：15 = 2×7 + 1，7 = 7×1 + 0，故 gcd = 1。该算法的时间复杂度为 O(log N)，即使 N 达到数百位也能瞬间完成。在 Shor 算法的经典后处理阶段，gcd 还会再次出场：由求得的周期 r 计算 gcd(a^r/2 − 1, N) 与 gcd(a^r/2 + 1, N)，从而提取因子。因此 gcd 贯穿算法首尾，是最基础也最不可省略的运算。

三、欧拉定理：为乘法阶提供存在性保证

欧拉函数 φ(N) 表示 1 到 N 中与 N 互素的整数个数。对 N = 15，与它互素的数是 1、2、4、7、8、11、13、14，共 8 个，故 φ(15) = 8。若 N = pq 为两个不同素数之积，则 φ(N) = (p−1)(q−1)，这一公式在 RSA 与 Shor 算法的分析中反复出现。

欧拉定理指出：若 gcd(a, N) = 1，则 a^φ(N) ≡ 1 (mod N)。这条定理的意义在于“保证存在性”——它告诉我们，只要 a 与 N 互素，模幂序列 a¹, a², a³, … 迟早会回到 1，绝不会无限发散。以 N = 15、a = 7 为例，φ(15) = 8，验证 7⁸ mod 15：由前面 7⁴ ≡ 1，故 7⁸ ≡ 1² = 1，与定理一致。欧拉定理并不直接给出“第一次回到 1”的位置，但它是乘法阶概念成立的基石，也是分析周期上界的依据。

四、乘法阶：Shor 算法真正要测量的量

在 gcd(a, N) = 1 的前提下，使得 a^r ≡ 1 (mod N) 成立的最小正整数 r，称为 a 模 N 的乘法阶，记作 ord_N(a)。它是 Shor 算法的核心目标：量子部分所做的一切，本质上就是在求这个 r。仍以 N = 15、a = 7 为例，逐次计算可得 7¹ ≡ 7、7² ≡ 4、7³ ≡ 13、7⁴ ≡ 1，因此 ord₁₅(7) = 4。而若取 a = 2，则 2¹ ≡ 2、2² ≡ 4、2³ ≡ 8、2⁴ ≡ 1，阶为 4；取 a = 4，则 4¹ ≡ 4、4² ≡ 1，阶为 2。可见不同底数的阶不同，且阶总是 φ(N) 的约数——这是欧拉定理与阶的定义共同推出的重要性质。

乘法阶有两条性质对算法成败至关重要。第一，r 必整除 φ(N)，因此 r ≤ φ(N) < N，搜索范围有限。第二，若 r 为偶数，则 a^r/2 是模 N 意义下 1 的一个“非平凡平方根”，即 (a^r/2)² ≡ 1 但 a^r/2 ≢ ±1，此时 gcd(a^r/2 ± 1, N) 有很大概率给出 N 的非平凡因子。若 r 为奇数，或 a^r/2 ≡ −1 (mod N)，则本次选取的 a 失败，需要换一个底数重试。这正是 Shor 算法外层循环存在的根本原因。

五、把四个工具串起来：一个可手算的完整示例

为了看清四者的衔接，取 N = 15 走一遍经典可验证的流程。第一步，随机取 a = 7，计算 gcd(7, 15) = 1，通过筛选。第二步，由欧拉定理知阶存在且整除 φ(15) = 8，可能的阶为 1、2、4、8。第三步，逐次计算模幂：7¹ ≡ 7、7² ≡ 4、7³ ≡ 13、7⁴ ≡ 1，得到 r = 4，为偶数。第四步，计算 a^r/2 = 7² ≡ 4 (mod 15)，检查 4 ≢ −1 (mod 15)，条件满足。第五步，求 gcd(4−1, 15) = gcd(3, 15) = 3，gcd(4+1, 15) = gcd(5, 15) = 5，于是 15 = 3 × 5 分解成功。

若换一个底数 a = 4，则 gcd(4, 15) = 1，模幂序列为 4、1，阶 r = 2。此时 a^r/2 = 4 ≡ −11 ≡ 4，而 −1 mod 15 等于 14，故 4 ≢ −1，条件仍满足，gcd(4−1, 15) = 3、gcd(4+1, 15) = 5，同样成功。但若取 a = 14，则 14 ≡ −1，14² ≡ 1，阶 r = 2，而 a^r/2 = 14 ≡ −1 (mod 15)，落入失败分支，必须换底数。这个对比说明：阶为偶数只是必要条件，a^r/2 ≢ −1 才是真正决定能否提取因子的判据，而这一判据的成立概率与 N 的素因子结构有关，通常一次成功的概率不低于 1/2，重试几次即可稳定得到结果。

总结来看，模运算提供了运算的“舞台”，gcd 负责筛选与最终提取因子，欧拉定理保证了阶的存在性与上界，乘法阶则是量子部分唯一需要测量的目标量。四者不是并列的知识点，而是一条从输入到输出的因果链：没有互素筛选，阶无从谈起；没有欧拉定理，不知道搜索边界；没有阶的偶性与非平凡平方根判据，就无法把周期翻译成因子。理解这条链，再去读 Shor 算法的量子线路，就不会把“求周期”当成一个孤立的黑箱，而能清楚知道每一步在数论上对应什么、失败时该检查哪个条件。