AKS素数判定法のソースを表示

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

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

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

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

== 発想 ==
AKS素数判定法は、ある意味では[[フェルマーの小定理#フェルマーテスト|フェルマーテスト]]の改良と見ることができる。

[[フェルマーの小定理]]の[[対偶 (論理学)|対偶]]である次のような命題を考える。
: <math>a</math>, <math>n</math> が[[互いに素]]な[[自然数]]であるとする。
::<math>a^n \ \not\equiv\ a \pmod{n}</math>
: であるとき、<math>n</math> は[[合成数]]である。
フェルマーテストはこの十分条件によって[[素数判定|確率的素数判定]]を行うものであったが、上は必要条件ではないので、合成数であるにもかかわらずそれを検出できない場合があった。特に、'''カーマイケル数'''と呼ばれる合成数が無限個存在し、これらはいかなる <math>a</math> を用いても合成数であることを検出できない。

そこで、この条件を次のように改良する。
:<math>a</math>, <math>n</math> が互いに素な自然数であるとする。
:: <math>(X+a)^n \ \not\equiv\ X^n+a \pmod{n}</math>
:のとき、かつそのときに限り、(iff:if and only if) <math>n</math> は合成数である。
このことは、[[二項定理]]により各次数の係数を評価すれば容易に証明できる。

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

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

そこでもう少し大雑把に評価することにする。具体的には、何らかの小さい <math>r</math> をとって <math>X^r-1</math> を法として評価する。すると、<math>X^r-1</math> による剰余は[[高々 (数学)|高々]] <math>r-1</math> 次だから、評価する係数の数を減らすことができる。
:<math>(X+a)^n \ \not\equiv\ X^n+a \pmod{X^r-1,n}</math> 
しかし、これは「大雑把な評価」である。評価を楽にした分、その精度も落ちている。このままでは、合成数なのに誤って素数であると判定してしまう恐れがある。そこで、パラメータ <math>a</math> を動かして、たくさんの <math>a</math> に対して上の合同式を評価することで埋め合わせにする。

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

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

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

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

ただし、記法 <math>\tilde{O}</math> は、次のように定義される。
:<math>f(x) = \tilde{O}(g(x)) \Leftrightarrow f(x) = O(g(x)\cdot \mathrm{Poly}(\log g(x)))</math>
即ち、記号 <math>\tilde{O}</math> は[[ランダウの記号]] ''O'' を少しだけ弱めたものである。<math>f(x) = \tilde{O}(g(x))</math> ならば、任意の <math>\epsilon > 0</math> について <math>f(x) = O\left(g(x)^{1+\epsilon}\right)</math> が成立する（逆は成り立たない）。

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

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

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

更に、いくつかの証明されていない仮説を認めるならば、<math>r</math> の評価をより小さくできる。
* [[アルチン予想]]を認めるならば <math>r = O(\log(n)^2)</math> である。
* [[ソフィー・ジェルマン素数]]の密度予想が正しいと仮定すれば、<math>r = \tilde{O}(\log(n)^2)</math> である。
これらの仮説はともに[[リーマン予想|一般リーマン仮説]]を認めれば証明できる。多くの[[数学者]]がリーマン仮説は正しいと信じていることを考えれば、<math>r=O(\log(n)^2)</math> つまり、AKSアルゴリズムの時間的計算量が <math>\tilde{O}(\log(n)^6)</math> である見込みは高い。

== 関連項目 ==
* [[素数]]
* [[素数判定]]

== 外部リンク ==
* [http://www.cse.iitk.ac.in/users/manindra/ Manindra's home page] - Agrawal教授のサイト
** [http://www.cse.iitk.ac.in/users/manindra/algebra/primality_original.pdf Agrawal, M., Kayal, N., and Saxena, N.: ''Primes in P'', Aug. 6, 2002] - 原著論文
** [http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf ''PRIMES is in P'', August, 2005 version] - 6訂版

* [http://www.h4.dion.ne.jp/~a00/ms_project_jp.html 原著論文の日本語による解説のサイト]

[[Category:数論アルゴリズム|えいけいえすそすうはんていほう]]
[[Category:数学に関する記事|AKSえいけいえすそすうはんていほう]]
[[Category:素数]]