AKS素数判定法
AKS素数判定法(AKSそすうはんていほう)は、与えられた自然数が素数であるかどうかを決定的多項式時間で判定できる、世界初のアルゴリズムである。ここで、素数判定法が多項式時間であるとは、与えられた自然数 n {\displaystyle n} が素数であるかどうかを判定するのにかかる時間が log  ( n ) {\displaystyle \log(n)} の多項式を上界とすることをいう。 n {\displaystyle n} の多項式ではないことに注意する必要がある。
AKS素数判定法は2002年8月6日に "PRIMES is in P" と題された論文で発表された。Agrawal-Kayal-Saxena 素数判定法としても知られ、論文の著者であるインド工科大学のマニンドラ・アグラワル教授と、2人の学生ニラジュ・カヤル、ナイティン・サクセナ(英語版)の3人の名前から付けられた。
この素数判定法が発見される以前にも、素数の判定方法は多数知られていたが、リーマン予想などの仮説を用いずに、決定的多項式時間で判定できるアルゴリズムは存在しなかった。
素数判定という重要な問題が実際にクラスPに属することを示した点で理論的には大躍進であった。しかし実用的には、多項式の次数が高すぎるので、今まで判定できなかった素数を高速に判定できるようになったわけではない(まだ「一般数体篩法」で因数分解した方がよい)。
第4ステップでは、もしこの段階で n ≤ r {\displaystyle n\leq r} であったならば、第3ステップにおいて n {\displaystyle n} が n − 1 {\displaystyle n-1} までのすべての数と互いに素であると確認したことになるから、「素数である」と出力して終了する。これは、 n {\displaystyle n} が非常に小さい数の場合に発生するケースであり、400 より大きい n {\displaystyle n} についてはあまり起こらない。
第5ステップは、アルゴリズムの中心的な部分である。ここでいずれかの a {\displaystyle a} についてこの合同式が不成立であれば、 n {\displaystyle n} は合成数である。このことは二項定理を用いて係数を真面目に評価すれば容易に証明できる。
第5ステップにおいて、十分に多くの a {\displaystyle a} を用いても合成数であることを検出できなかったなら、そのとき n {\displaystyle n} は実際に素数である。このことがAKSアルゴリズムの中核であり、PRIMES is in P の半ばはその証明に費やされている。
ただし、記法 O ~ {\displaystyle {\tilde {O}}} は、次のように定義される。
f ( x ) = O ~ ( g ( x ) ) ⇔ f ( x ) = O ( g ( x ) ⋅ P o l y ( log  g ( x ) ) ) {\displaystyle f(x)={\tilde {O}}(g(x))\Leftrightarrow f(x)=O(g(x)\cdot \mathrm {Poly} (\log g(x)))}
即ち、記号 O ~ {\displaystyle {\tilde {O}}} はランダウの記号 O を少しだけ弱めたものである。 f ( x ) = O ~ ( g ( x ) ) {\displaystyle f(x)={\tilde {O}}(g(x))} ならば、任意の ε > 0 {\displaystyle \epsilon >0} について f ( x ) = O ( g ( x ) 1 + ε ) {\displaystyle f(x)=O\left(g(x)^{1+\epsilon }\right)} が成立する(逆は成り立たない)。