AKS 算法：素数判定属于 P 类问题的证明

历史背景与问题演进

素性检验的历史可追溯至古希腊时期的埃拉托色尼筛法，但其时间复杂度为，对大整数而言本质上是指数级增长。17 世纪费马小定理启发了概率性检验方法，如费马素性检验，虽将复杂度降至，却无法避免卡迈克尔数导致的误判。20 世纪 70 年代出现的米勒 - 拉宾检验虽降低了错误概率，但仍依赖未证明的广义黎曼猜想才能确保确定性。APR 算法虽实现多项式时间复杂度，却受限于特定数域且证明复杂。这些局限性使得 "素数判定是否存在无条件多项式时间算法" 成为理论计算机科学的重要开放问题。

2002 年，Agrawal、Kayal 和 Saxena（当时为本科生）基于有限域多项式理论提出 AKS 算法，其核心创新在于将素性判定转化为多项式同余方程的验证问题。该算法不依赖任何未证明猜想，在 时间内确定性地完成素性检验，最终确立 PRIMES 属于 P 类。这一成果被评价为 "21 世纪最重要的算法之一"，三人因此获得 2006 年哥德尔奖和富尔克森奖。

核心数学原理与定义

AKS 算法的理论基础建立在以下关键定义和定理之上：

分圆多项式与阶的概念

定义 1（阶，Order）：对于互素整数 和， 模 的阶 是满足 的最小正整数。若 与 不互素，则 无定义。

定义 2（分圆多项式）： 次分圆多项式 定义为所有 次本原单位根的极小多项式，即。其重要性质包括：

• 是整系数多项式
• 若 是素数且，则 当且仅当

AKS 主定理

定理（AKS 主定理）：整数 是素数，当且仅当：

1. 不是完全幂（即不存在 使得）
2. 存在整数 满足
3. 对所有，多项式同余式 成立

该定理将素性判定转化为三个条件的验证，其中多项式同余条件是核心。其本质是费马小定理在多项式环上的推广：对素数， 恒成立；通过模 运算，将无限项多项式比较转化为有限项比较，从而实现复杂度控制。

算法步骤与复杂度分析

AKS 算法完整流程

输入：整数

1. 完全幂检查：若存在 使得，输出 "合数"

   实现方法：对 从 2 到 枚举，通过二分法检查是否存在整数 满足。时间复杂度

2. 寻找合适的：找到最小的 使得。若，输出 "素数"

   理论依据：数论中的存在性定理保证这样的 不超过。实际寻找时通过枚举 并验证对所有，

3. 小因子检查：对 从 2 到，若，输出 "合数"

   作用：排除与 不互素的合数，简化后续多项式验证

4. 多项式同余验证：对 从 1 到，若，输出 "合数"

   核心步骤：通过快速多项式乘法和模约简，在 时间内验证每个同余式

5. 输出结果：若所有检查通过，输出 "素数"

复杂度推导

步骤 2（寻找）：根据素数定理，在区间 内素数个数约为。取，则需检查 个，每个检查涉及 次模指数运算，总复杂度

步骤 4（多项式验证）：需验证 个 值。由于，故，因此 的数量级为。每个多项式同余验证通过分治乘法实现，复杂度，故总复杂度

整体复杂度：通过优化 的选取和多项式乘法算法，最终可将复杂度降至。Lenstra 和 Pomerance 进一步改进到，但证明更为复杂

多项式同余核心证明

AKS 算法正确性的关键在于证明：若 是合数且通过所有检查，则 必为素数幂。以下是关键步骤的形式化证明：

引理 1（素数的多项式同余性质）

若 是素数，则对任意，有

证明：由二项式定理展开。对素数，当 时，，故。由费马小定理，因此。模 运算不影响该同余关系，因为两边多项式的对应系数模 均相等

引理 2（合数的排除条件）

设 是合数且非素数幂， 满足，且对所有 有，则存在素因子 使得

证明：令 是 的最小素因子，设。由于 非素数幂，存在另一个素因子。由多项式同余条件模 成立，即。根据有限域理论，多项式 在 中有至少 个根（即）。由因子定理， 的次数为，而其分裂域的阶不超过。通过比较根的数量与域大小，可推出，与 矛盾

主定理证明（反证法）

假设 是合数且通过所有 AKS 检查：

1. 步骤 1 排除了素数幂，故 有至少两个不同素因子
2. 步骤 3 确保 与 互素，故 有定义
3. 引理 2 指出此时存在素因子 使得，但这与步骤 2 中 的选取矛盾

因此 必为素数

实际应用与理论影响

尽管 AKS 算法在理论上具有里程碑意义，但其实际性能仍无法与概率算法竞争。测试显示，对于 5 位素数，AKS 算法需要 20-80 秒，而米勒 - 拉宾检验可在微秒级完成。这种差距源于多项式模运算的高常数因子，使得 AKS 算法主要用于理论证明而非实际素性检验

在理论层面，AKS 算法的贡献体现在：

1. 计算复杂性：彻底解决 PRIMES 是否属于 P 类的问题，为其他数论问题的复杂性研究提供范式
2. 算法设计：展示了代数方法在复杂性理论中的强大作用，启发后续如椭圆曲线素性检验等算法的改进
3. 形式化验证：推动了 HOL4 等定理证明器对复杂算法的机械化验证，促进了数学证明的计算机辅助实现

AKS 算法的故事也具有深刻的启示意义：三位印度学者基于基础数学理论的创新，解决了困扰学界数十年的难题。这提醒我们，在追求实用算法的同时，纯理论研究往往能带来意想不到的突破。随着量子计算的发展，AKS 算法的思想或许会在新的计算模型中焕发新的生命力，正如它当初颠覆传统素性检验认知那样。