Aks素数判定法: 素数に関するアルゴリズム

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

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

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

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

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

${\displaystyle a}$ , ${\displaystyle n}$  が互いに素な自然数であるとする。
${\displaystyle a^{n}\ \not \equiv \ a{\pmod {n}}}$ 
であるとき、${\displaystyle n}$  は合成数である。

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

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

${\displaystyle a}$ , ${\displaystyle n}$  が互いに素な自然数であるとする。
${\displaystyle (X+a)^{n}\ \not \equiv \ X^{n}+a{\pmod {n}}}$ 
であることは、 ${\displaystyle n}$  は合成数であることと同値である。

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

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

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

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

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

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

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

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

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

ただし、上において、

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

解説

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

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

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

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

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

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

各ステップの評価

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

したがって、全体の時間は ${\displaystyle {\tilde {O}}(\log(n)^{10.5})}$  であるといえる。

評価の改良

全体の時間を支配しているのは、第5ステップの時間であり、ひいては ${\displaystyle r}$  の大きさである。したがって、実は ${\displaystyle r}$  は ${\displaystyle \lceil 16\log(n)^{5}\rceil }$  よりも小さく定まるということを証明できれば、計算量の評価を改善することができる。

• 篩理論より ${\displaystyle r=O(\log(n)^{3})}$  であるということが分かるので、実際にはアルゴリズムは ${\displaystyle {\tilde {O}}(\log(n)^{7.5})}$  で動作する。

更に、いくつかの証明されていない仮説を認めるならば、${\displaystyle r}$  の評価をより小さくできる。

• アルチン予想を認めるならば ${\displaystyle r=O(\log(n)^{2})}$  である。
• ソフィー・ジェルマン素数の密度予想が正しいと仮定すれば、${\displaystyle r={\tilde {O}}(\log(n)^{2})}$  である。

これらの仮説はともに一般リーマン仮説を認めれば証明できる。多くの数学者がリーマン仮説は正しいと信じていることを考えれば、${\displaystyle r=O(\log(n)^{2})}$  つまり、AKSアルゴリズムの時間的計算量が ${\displaystyle {\tilde {O}}(\log(n)^{6})}$  である見込みは高い。

• 素数
• 素数判定

• Manindra's home page - Agrawal教授のサイト
  • Agrawal, M., Kayal, N., and Saxena, N.: Primes in P, Aug. 6, 2002 - 原著論文
  • PRIMES is in P, August, 2005 version - 6訂版

• 原著論文の日本語による解説のサイト - ウェイバックマシン（2003年6月5日アーカイブ分）
• 小澤伸二, 宮田大輔: AKS予想の実装と検証, パソコンリテラシ, 28(5), (2003)，8-13