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人の学生ニラジュ・カヤル、ナイティン・サクセナ（Nitin Saxena）の3人の名前から付けられた。

この素数判定法が発見される以前にも、素数の判定方法は多数知られていたが、リーマン予想などの仮説を用いずに、決定的多項式時間で判定できるアルゴリズムは存在しなかった。

素数判定という重要な問題が実際にクラスPに属することを示した点で理論的には大躍進であった。しかし実用的には、多項式の次数が高すぎるので、今まで判定できなかった素数を高速に判定できるようになったわけではない（まだ「一般数体ふるい法」で因数分解した方がよい）。目次

1 発想

2 アルゴリズム

2.1 解説


3 時間的計算量

3.1 各ステップの評価

3.2 評価の改良


4 関連項目

5 外部リンク

発想

AKS素数判定法は、ある意味ではフェルマーテストの改良と見ることができる。

フェルマーの小定理の対偶である次のような命題を考える。 a {\displaystyle a} , n {\displaystyle n} が互いに素な自然数であるとする。 a n   ≢   a ( mod n ) {\displaystyle a^{n}\ \not \equiv \ a{\pmod {n}}} であるとき、 n {\displaystyle n} は合成数である。

フェルマーテストはこの十分条件によって確率的素数判定を行うものであったが、上は必要条件ではないので、合成数であるにもかかわらずそれを検出できない場合があった。特に、カーマイケル数と呼ばれる合成数が無限個存在し、これらはいかなる a {\displaystyle a} を用いても合成数であることを検出できない。

そこで、この条件を次のように改良する。 a {\displaystyle a} , n {\displaystyle n} が互いに素な自然数であるとする。 ( X + a ) n   ≢   X n + a ( mod n ) {\displaystyle (X+a)^{n}\ \not \equiv \ X^{n}+a{\pmod {n}}} のとき、かつそのときに限り、(iff:if and only if) n {\displaystyle n} は合成数である。

このことは、二項定理により各次数の係数を評価すれば容易に証明できる。

上の式は、 X {\displaystyle X} が恒等的に 0 だと思えばフェルマーの小定理の対偶そのものである。つまり、上の条件による判定はフェルマーテストをより厳密にしたものといえる。

厳密にしたことによりフェルマーテストとは異なり必要十分条件を与えている。したがって上の合同式を真面目に評価してやれば素数性を判定する決定性アルゴリズムができるが、これは時間がかかりすぎる。つまり、最悪の場合 n {\displaystyle n} 個の係数を評価しなければならないので、これは n {\displaystyle n} のビット数に対して指数関数時間である。

そこでもう少し大雑把に評価することにする。具体的には、何らかの小さい r {\displaystyle r} をとって X r − 1 {\displaystyle X^{r}-1} を法として評価する。すると、 X r − 1 {\displaystyle X^{r}-1} による剰余は高々 r − 1 {\displaystyle r-1} 次だから、評価する係数の数を減らすことができる。 ( X + a ) n   ≢   X n + a ( mod X r − 1 , n ) {\displaystyle (X+a)^{n}\ \not \equiv \ X^{n}+a{\pmod {X^{r}-1,n}}}

しかし、これは「大雑把な評価」である。評価を楽にした分、その精度も落ちている。このままでは、合成数なのに誤って素数であると判定してしまう恐れがある。そこで、パラメータ a {\displaystyle a} を動かして、たくさんの a {\displaystyle a} に対して上の合同式を評価することで埋め合わせにする。

この発想が、AKSアルゴリズムの肝である。つまり、十分にたくさんの a {\displaystyle a} について上の合同式を確かめれば、 X r − 1 {\displaystyle X^{r}-1} を法としたままでも素数性を厳密に判定することができる（これは自明ではないが、証明できる）。そして、 a {\displaystyle a} を動かす範囲や適切な r {\displaystyle r} の値は n {\displaystyle n} に対してそれほど大きくならないので、この方法は最初の合同式を真面目に評価するより速く、多項式時間で動作する。
アルゴリズム

素数性を判定すべき、2以上の自然数 n {\displaystyle n} を入力する。
もし、 n {\displaystyle n} が累乗数であるならば「合成数である」と出力してアルゴリズムを終了する。

o r ( n ) > 4 log 2 ⁡ n {\displaystyle o_{r}(n)>4\log ^{2}n} になる最小の r {\displaystyle r} を見つける。