AKS素数判定法（-そすうはんていほう）は、与えられた自然数が素数であるかどうかを決定的多項式時間で判定できる、世界初のアルゴリズムである。ここで、素数判定法が多項式時間であるとは、与えられた自然数 formula_1 が素数であるかどうかを判定するのにかかる時間がformula_2 の多項式を上界とすることをいう。formula_1 の多項式ではないことに注意する必要がある。AKS素数判定法は2002年8月6日に "PRIMES is in P" と題された論文で発表された。Agrawal-Kayal-Saxena 素数判定法としても知られ、論文の著者であるインド工科大学のマニンドラ・アグラワル教授と、2人の学生ニラジュ・カヤル、ナイティン・サクセナ（Nitin Saxena）の3人の名前から付けられた。この素数判定法が発見される以前にも、素数の判定方法は多数知られていたが、リーマン予想などの仮説を用いずに、決定的多項式時間で判定できるアルゴリズムは存在しなかった。素数判定という重要な問題が実際にクラスPに属することを示した点で理論的には大躍進であった。しかし実用的には、多項式の次数が高すぎるので、今まで判定できなかった素数を高速に判定できるようになったわけではない（まだ「一般数体ふるい法」で因数分解した方がよい）。AKS素数判定法は、ある意味ではフェルマーテストの改良と見ることができる。フェルマーの小定理の対偶である次のような命題を考える。フェルマーテストはこの十分条件によって確率的素数判定を行うものであったが、上は必要条件ではないので、合成数であるにもかかわらずそれを検出できない場合があった。特に、カーマイケル数と呼ばれる合成数が無限個存在し、これらはいかなる formula_4 を用いても合成数であることを検出できない。そこで、この条件を次のように改良する。このことは、二項定理により各次数の係数を評価すれば容易に証明できる。上の式は、formula_13 が恒等的に 0 だと思えばフェルマーの小定理の対偶そのものである。つまり、上の条件による判定はフェルマーテストをより厳密にしたものといえる。厳密にしたことによりフェルマーテストとは異なり必要十分条件を与えている。したがって上の合同式を真面目に評価してやれば素数性を判定する決定性アルゴリズムができるが、これは時間がかかりすぎる。つまり、最悪の場合 formula_1 個の係数を評価しなければならないので、これは formula_1 のビット数に対して指数関数時間である。そこでもう少し大雑把に評価することにする。具体的には、何らかの小さい formula_16 をとって formula_17 を法として評価する。すると、formula_17 による剰余は高々 formula_19 次だから、評価する係数の数を減らすことができる。しかし、これは「大雑把な評価」である。評価を楽にした分、その精度も落ちている。このままでは、合成数なのに誤って素数であると判定してしまう恐れがある。そこで、パラメータ formula_4 を動かして、たくさんの formula_4 に対して上の合同式を評価することで埋め合わせにする。この発想が、AKSアルゴリズムの肝である。つまり、十分にたくさんの formula_4 について上の合同式を確かめれば、formula_17 を法としたままでも素数性を厳密に判定することができる（これは自明ではないが、証明できる）。そして、formula_4 を動かす範囲や適切な formula_16 の値は formula_1 に対してそれほど大きくならないので、この方法は最初の合同式を真面目に評価するより速く、多項式時間で動作する。素数性を判定すべき、2以上の自然数 formula_1 を入力する。ただし、上において、AKSアルゴリズムの時間的計算量は高々 formula_66 である。"PRIMES is in P" の初版では、このアルゴリズムは formula_67 のアルゴリズムとして提示された。その後の改訂を経て、現在では formula_66 であることが証明されている。しかし、実際には formula_69 であろうと考えられている。また、現在の証明は篩理論の高度な結果によっているが、初歩的な代数学の知識だけでも formula_70 であることは証明できる。ただし、記法 formula_71 は、次のように定義される。即ち、記号 formula_71 はランダウの記号 "O" を少しだけ弱めたものである。formula_74 ならば、任意の formula_75 について formula_76 が成立する（逆は成り立たない）。したがって、全体の時間は formula_70 であるといえる。全体の時間を支配しているのは、第5ステップの時間であり、ひいては formula_16 の大きさである。したがって、実は formula_16 は formula_99 よりも小さく定まるということを証明できれば、計算量の評価を改善することができる。更に、いくつかの証明されていない仮説を認めるならば、formula_16 の評価をより小さくできる。これらの仮説はともに一般リーマン仮説を認めれば証明できる。多くの数学者がリーマン仮説は正しいと信じていることを考えれば、formula_105 つまり、AKSアルゴリズムの時間的計算量が formula_69 である見込みは高い。

出典:wikipedia