4. 周期求解问题的数学定义

Shor 算法之所以能够分解大整数，关键并不在于量子傅里叶变换本身，而在于它把"分解整数"这个数论难题，巧妙地转化为"求某个模幂函数的周期"这一代数问题。本节要讲清楚的就是这个转化的数学定义：函数 f(x)=a^x mod N 到底具有怎样的周期性，周期 r 是什么，以及为什么一旦求出 r，就能以较高概率得到 N 的一个非平凡因子。

一、模幂函数的定义与周期性

设 N 为待分解的合数，a 为满足 1<a<N 且 gcd(a,N)=1 的整数（即 a 与 N 互素）。定义函数：

f(x) = a^x mod N,   x = 0, 1, 2, 3, ...

由于模 N 的余数只有 0 到 N−1 共 N 种取值，而 x 可以无限增大，根据抽屉原理，序列 f(0), f(1), f(2), … 必然会出现重复。更进一步，因为 a 与 N 互素，a^x 永远不可能被 N 整除，所以 f(x) 的取值全部落在 {1,2,…,N−1} 中，且 f(0)=1。

可以证明该序列是纯周期序列：存在最小正整数 r，使得对所有 x≥0 都有

f(x + r) = f(x)  即  a^(x+r) ≡ a^x (mod N)

这个最小的 r 就称为 a 模 N 的乘法阶（multiplicative order），也就是我们要找的周期。由 a 与 N 互素，两边可约去 a^x，得到等价定义：

a^r ≡ 1 (mod N)，且 r 是满足此式的最小正整数

例如取 N=15、a=2：2^0=1，2^1=2，2^2=4，2^3=8，2^4=16≡1，于是 r=4。序列 1,2,4,8,1,2,4,8,… 以 4 为周期循环。再取 N=15、a=7：7^1=7，7^2=49≡4，7^3≡28≡13，7^4≡91≡1，得 r=4。可见同一个 N 下，不同的 a 可能给出不同的周期，但周期总是存在的。

二、周期 r 与因数分解的归约关系

求出 r 之后，如何得到 N 的因子？核心依据是下面这个恒等式。由 a^r ≡ 1 (mod N) 可知 N 整除 a^r − 1。若 r 为偶数，令 r=2k，则

a^r − 1 = (a^k − 1)(a^k + 1)

N 整除这个乘积，但通常 N 并不整除单独的 (a^k − 1)（因为 r 是最小周期，a^k ≢ 1），也不一定整除 (a^k + 1)。当 N 的因子"分裂"到这两个因式中时，通过计算

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

就能得到 N 的非平凡因子。这就是从周期到因子的归约：把"分解 N"归约为"求 a 模 N 的阶 r"，再用一次最大公约数计算收尾。

归约成立需要满足两个条件，缺一不可：

• r 是偶数：若 r 为奇数，则 r/2 不是整数，无法做上面的平方差分解。
• a^(r/2) ≢ −1 (mod N)：若 a^(r/2) ≡ −1，则 a^(r/2)+1 ≡ 0，gcd 结果会退化为 N 本身，得不到真因子。

可以证明：在 1<a<N 且 gcd(a,N)=1 中随机选取 a，上述两个条件同时成立的概率至少为 1/2。因此只要随机多试几个 a，就能以很高概率成功。这正是 Shor 算法外层"随机选 a—量子求 r—经典求 gcd"循环的数学依据。

三、完整归约流程与示例

把上述逻辑串起来，从 N 到因子的完整路径如下：随机选取 a → 判断 gcd(a,N) 是否大于 1 → 若互素则求周期 r → 检查 r 是否为偶数、a^(r/2) 是否不等于 −1 → 计算两个 gcd 得到因子。下面这张图刻画了周期 r 与因数分解之间的归约关系及判断分支。

以 N=15、a=2 为例走一遍：gcd(2,15)=1，互素，进入求周期；得到 r=4，为偶数；a^(r/2)=2^2=4，4 mod 15=4≠−1（即不等于 14），条件满足；计算 gcd(4−1,15)=gcd(3,15)=3，gcd(4+1,15)=gcd(5,15)=5，于是 15=3×5 被成功分解。整个过程只用到一次量子求周期和两次经典 gcd。

四、为什么这个归约对 Shor 算法至关重要

从计算复杂度看，经典计算机上求 a 模 N 的阶 r，目前没有已知的多项式时间算法，这正是 RSA 安全性的来源之一。而 Shor 算法利用量子傅里叶变换，可以在多项式时间内以高概率求出 r。归约的意义在于：它把"整数分解"这一困难问题，等价地转化为"求模幂函数周期"这一量子计算机擅长的问题。因此，理解 f(x)=a^x mod N 的周期性、周期 r 的定义，以及 r 到因子的 gcd 归约，是掌握 Shor 算法整体逻辑的数学基石。

小结本节要点：f(x)=a^x mod N 是纯周期函数，最小正周期 r 满足 a^r≡1 (mod N)；当 r 为偶数且 a^(r/2)≢−1 时，gcd(a^(r/2)±1, N) 给出 N 的非平凡因子；随机选取 a 时该条件成立的概率不低于 1/2，因此重复尝试即可高概率完成分解。这条"周期→因子"的归约链，正是后续量子线路设计要实现的数学目标。