知识/定理
阿格拉瓦尔-卡亚尔-萨克塞纳（2002）AKS：多项式时间内确定性判定素数——200 年开放问题的解决。
公式
$(x-a)^n\equiv x^n-a\pmod{(x^r-1,n)}$ 对若干 $a,r$ 成立 ⟺ $n$ 为素幂。
证明思路
（有限域+组合）借多项式同余条件刻画素数，复杂度 $O(\log^{O(1)}n)$。
应用/例子
密码学密钥生成（RSA）、素性证明工具。
意义/影响
首个无条件多项式时间确定性素性测试；算法数论的里程碑。
DOXA · 数学编年史 · 知识详情
2002 ｜ 阿格拉瓦尔等 ｜ 代数·数论 ｜ 突破
阿格拉瓦尔-卡亚尔-萨克塞纳（2002）AKS：多项式时间内确定性判定素数——200 年开放问题的解决。
$(x-a)^n\equiv x^n-a\pmod{(x^r-1,n)}$ 对若干 $a,r$ 成立 ⟺ $n$ 为素幂。
（有限域+组合）借多项式同余条件刻画素数，复杂度 $O(\log^{O(1)}n)$。
密码学密钥生成（RSA）、素性证明工具。
首个无条件多项式时间确定性素性测试；算法数论的里程碑。