AKS素数判定法

AKS素数判定法（AKSそすうはんていほう）は、与えられた自然数が素数であるかどうかを決定的多項式時間で判定できる、世界初のアルゴリズムである。ここで、素数判定法が多項式時間であるとは、与えられた自然数 $n$ が素数であるかどうかを判定するのにかかる時間が $\log(n)$ の多項式を上界とすることをいう。 $n$ の多項式ではないことに注意する必要がある。

AKS素数判定法は2002年 8月6日に "PRIMES is in P" と題された論文で発表された。Agrawal-Kayal-Saxena 素数判定法としても知られ、論文の著者であるインド工科大学のマニンドラ・アグラワル教授と、2人の学生ニラジュ・カヤル、ナイティン・サクセナ（英語版）の3人の名前から付けられた。

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

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

発想

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

フェルマーの小定理の対偶である次のような命題を考える。

a

,

n

が互いに素な自然数であるとする。

a^{n}\ \not \equiv \ a{\pmod {n}}

であるとき、

n

は合成数である。

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

そこで、この条件を次のように改良する。

a

,

n

が互いに素な自然数であるとする。

(X+a)^{n}\ \not \equiv \ X^{n}+a{\pmod {n}}

であることは、

n

は合成数であることと同値である。

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

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

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

そこでもう少し大雑把に評価することにする。具体的には、何らかの小さい $r$ をとって $X^{r}-1$ を法として評価する。すると、 $X^{r}-1$ による剰余は高々 $r-1$ 次だから、評価する係数の数を減らすことができる。

(X+a)^{n}\ \not \equiv \ X^{n}+a{\pmod {X^{r}-1,n}}

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

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

アルゴリズム

素数性を判定すべき、2以上の自然数 $n$ を入力する。

もし、 $n$ が累乗数であるならば「合成数である」と出力してアルゴリズムを終了する。
$o_{r}(n)>4\log ^{2}n$ になる最小の $r$ を見つける。
もし、ある $a\leq r$ に対して $1<(a,n)<n$ ならば、「合成数である」と出力してアルゴリズムを終了する。
もし、 $n\leq r$ ならば、「素数である」と出力してアルゴリズムを終了する。
$1$ から $[2{\sqrt {\phi (r)}}\log n]$ まで、順に $a$ を動かすものとする。もし $(X+a)^{n}\ \not \equiv \ X^{n}+a{\pmod {X^{r}-1,n}}$ ならば、「合成数である」と出力してアルゴリズムを終了する。
「素数である」と出力してアルゴリズムを終了する。

ただし、上において、

$(a,b)$ は $a$ , $b$ の最大公約数
$o_{r}(n)$ は $r$ を法とした $n$ の位数、つまり $n^{e}\equiv 1{\pmod {r}}$ なる最小の自然数 $e$ である。
$[x]$ はガウス記号
$\phi$ はオイラーのφ関数

解説

第5ステップで用いている判定法は、累乗数についてはうまく働かない。累乗数であるならばすなわち合成数なのだから、最初のステップにおいて累乗数であると判明した場合には「合成数である」と出力して終了する。
次に、 $n$ の位数が十分に大きくなるような法 $r$ を求める。このような $r$ が存在するのかどうかが問題となるが、最小公倍数に関する議論から $r\leq \lceil 16\log(n)^{5}\rceil$ までに存在することが示される。
その次に、 $n$ が実際に $(\mathbb {Z} /r\mathbb {Z} )^{\times }$ の元であるかを確かめている。これは第5ステップが正しく動作するために必要である。 $(\mathbb {Z} /r\mathbb {Z} )^{\times }$ に属する必要十分条件が (n, r) = 1 であるが、この段階で最大公約数が 1 でなかったなら、それはつまり $n$ の非自明な因数が発見されたということであるから、「合成数である」と出力して終了する。
第4ステップでは、もしこの段階で $n\leq r$ であったならば、第3ステップにおいて $n$ が $n-1$ までのすべての数と互いに素であると確認したことになるから、「素数である」と出力して終了する。これは、 $n$ が非常に小さい数の場合に発生するケースであり、400 より大きい $n$ についてはあまり起こらない。
第5ステップは、アルゴリズムの中心的な部分である。ここでいずれかの $a$ についてこの合同式が不成立であれば、 $n$ は合成数である。このことは二項定理を用いて係数を真面目に評価すれば容易に証明できる。
第5ステップにおいて、十分に多くの $a$ を用いても合成数であることを検出できなかったなら、そのとき $n$ は実際に素数である。このことがAKSアルゴリズムの中核であり、PRIMES is in P の半ばはその証明に費やされている。

時間的計算量

AKSアルゴリズムの時間的計算量は高々 ${\tilde {O}}(\log(n)^{7.5})$ である。

PRIMES is in P の初版では、このアルゴリズムは ${\tilde {O}}(\log(n)^{12})$ のアルゴリズムとして提示された。その後の改訂を経て、現在では ${\tilde {O}}(\log(n)^{7.5})$ であることが証明されている。しかし、実際には ${\tilde {O}}(\log(n)^{6})$ であろうと考えられている。また、現在の証明は篩理論の高度な結果によっているが、初歩的な代数学の知識だけでも ${\tilde {O}}(\log(n)^{10.5})$ であることは証明できる。

ただし、記法 ${\tilde {O}}$ は、次のように定義される。

f(x)={\tilde {O}}(g(x))\Leftrightarrow f(x)=O(g(x)\cdot \mathrm {Poly} (\log g(x)))

即ち、記号 ${\tilde {O}}$ はランダウの記号 O を少しだけ弱めたものである。 $f(x)={\tilde {O}}(g(x))$ ならば、任意の $\epsilon >0$ について $f(x)=O\left(g(x)^{1+\epsilon }\right)$ が成立する（逆は成り立たない）。

各ステップの評価

p進のニュートン法を用いれば、各自然数 $b$ について ${\sqrt[{b}]{n}}$ は ${\tilde {O}}(\log(n)^{2})$ で計算できる。 $n=a^{b}$ なる $b$ の上界は $\log _{2}n$ であるから、最初のステップは ${\tilde {O}}(\log(n)^{3})$ で動作する。
第2ステップは、 $r\leq \lceil 16\log(n)^{5}\rceil$ であったことを思い出せば、 ${\tilde {O}}(\log(n)^{7})$ で動作するといえる。
第3ステップでは、ユークリッドの互除法を用いれば最大公約数 1 つを ${\tilde {O}}(\log(n))$ で計算できる。これを $O(r)=O(\log(n)^{5})$ 回繰り返すので、第3ステップにかかる時間は ${\tilde {O}}(\log(n)^{6})$ である。
第4ステップは、単に比較するだけであるから $O(\log n)$ である。
第5ステップでは、 $\mod X^{r}-1$ で考えているので多項式の次数は高々 $r-1$ であり、 $\mod n$ で考えているので係数は高々 $n-1$ である。高速フーリエ変換を用いれば、このような多項式の冪は ${\tilde {O}}(r\log(n)^{2})$ で計算される。繰り返しの回数をかければ、第5ステップは ${\tilde {O}}(r{\sqrt {\phi (r)}}\log(n)^{3})={\tilde {O}}(\log(n)^{10.5})$ で動作するといえる。
第6ステップは、定数時間である。