最終更新日:2005.11.27
この文書は、Manindra's home pageにて公開されているPRIMES is in PのRevised paper version(3訂版)に基づいている。同論文の2005年11月27年現在の最新版はAUgust, 2005 version(6訂版)
AKSアルゴリズムについての概説は、Wikipediaの項目も参照。
AKSアルゴリズムとは、2002年8月6日に、PRIMES is in Pという論文の中に示された決定性多項式時間の素数判定アルゴリズムである。素数に関係する世界では大変話題になった。アルゴリズムの名前は、論文の著者であるインド工科大学計算機科学工学部のManindra Agrawal教授と、その学生であるNitin SaxenaおよびNeeraj Kayalに因む。
素数判定アルゴリズムが、未証明の仮説に依ることなく決定性多項式時間のものとしてきちんと証明されたのはこれが初めてのことであった。それ以前にも多数の素数判定アルゴリズムが示されていたが、以下のいずれかの問題があって、決定性多項式時間とは言い切れなかった。
AKSアルゴリズムは上のどの問題も抱えていない初めてのアルゴリズムであった。素数判定という理論上も応用上も極めて重要な問題が実際にクラスPに属すること言うことを示した点で、理論的には大躍進であった。
加えて言うならば、AKSは過去十年間に提案された幾つかの高速なアルゴリズムと比較してアルゴリズム自体が単純であり、しかも証明も初歩的な代数学の知識だけで理解できる易しいものである。このような重大な問題がこのように簡潔な形で解決されたことは、新鮮な驚きであり、数学者の感性から言えばある意味では「美しい」と言える。
「巨大な素数を生成する」という問題は、現代の暗号・セキュリティ技術の基盤として欠かせない。巨大な素数を生成するには、典型的には適当に大きな整数を作ってみて素数かどうか判定することになる。従って、素数性を高速に確実に判定するアルゴリズムは非常に重要である。
AKSアルゴリズムは現時点では多項式時間とは言ってもそれほど速いとは言えないようである。ラビン・ミラーの疑似素数判定法のように確率的ではあるが遥かに高速なアルゴリズムが幾つもあるので、実用上は多少不確実でもそれらを使った方がよい。
しかし、それでも「確実で多項式時間」なアルゴリズムを初めて作ったということは非常に重要である。また今後、このアルゴリズムを改良して実用に足る高速なアルゴリズムが開発される見込みが十分にある。
AKSアルゴリズムはある意味ではフェルマーテストの改良と言える。
次は、フェルマーの小定理の書き方の１つである。
a, nを互いに素な自然数とする。nが素数ならば次が満たされる。
これは、対偶を取ればnが合成数であるための十分条件を与えていると見ることができる。これを用いて擬素数判定を行うのがフェルマーテストであった。しかし、残念なことにこれは必要条件ではないので、素数性を厳密に判定することはできなかった。
そこで、フェルマーの小定理の多項式環への一般化にあたる次のような命題を考える。実際、Xが恒等的に0であると見なせばこれはフェルマーの小定理の式になる。
a, nを互いに素な自然数とする。次の式が成り立つことが、nが素数であることの必要十分条件である。
本題に直接は関係しないので証明は略す。
さて、上の合同式を真面目に評価してやれば素数性を判定する決定性アルゴリズムが出来るわけだが、生憎とこれは時間が掛かりすぎる。つまり、最悪の場合n個の係数を評価しなければならないので、これはnのビット数に対して指数時間である。
そこでもう少し大雑把に評価することにする。具体的には、何らかの小さいrをとって Xr-1 を法として評価する。すると、Xr-1による剰余は高々r-1次だから、評価する係数の数を減らすことが出来る。
しかし、これは「大雑把な評価」である。評価を楽にした分、その精度もかなりいい加減になっている。これままでは、合成数なのに誤って「素数」と判定してしまう恐れがある。そこで、aを動かして、たくさんのaに対して上の合同式を評価することで埋め合わせにする。
この発想が、AKSアルゴリズムの肝である。つまり、十分にたくさんのaについて上の合同式を確かめれば、Xr-1を法としたままでも素数性を厳密に判定することができる（これは自明ではないが、後述のように証明できる）。そして、aを動かす範囲や適切なrの値はnに対してそれほど大きくならないので、この方法は最初の合同式を真面目に評価するより速く、多項式時間で動作する。
このあたりで、厳密に記法を定義する。
(a,r)=1なる整数a, 自然数rに対し、「rを法とするaの位数」を「ak≡1 (mod r)なる最小の自然数k」と定義して、これを or(a) と書く。
(a,r)=1よりaは自然な凖同型によりZr*の元と見なすことができるので、or(a)とはaの群Zr*における位数である。
素数性を判定すべき、2以上の自然数nを入力する。
現在執筆中。
AKSアルゴリズムはO~(log7.5 n)で動作する。ただし、記号O~は次のように定義される。
つまり、記号 O~ はランダウの記号 O を少しだけ弱めた評価である。実際、f(t) = O~(g(t)) なるとき、任意のε > 0 について次が成り立つ。
前提として、自然数m, nの加減乗除はすべて O~(log max(m,n))で計算できるということを認めよう（そのうち、多倍長整数の項で扱うかも知れないが、とりあえずは何か適当な計算量理論の教科書を参照のこと）。
各自然数 k に対し、n の k 乗根を計算するための時間は O(log2 n) である。これはp進ニュートン法を用いればよい。これに関する詳細は次の資料を参照。
n = bk なる k の上界は k = log2 nであるから、step 1に要する時間は O(log3 nである。
各々のrの値に対して、or(n) > 4log2 nであるかどうかを確認するには実際にrを法としてnの冪を計算してみれば良い。つまり、次のような手順で確認できる。
各乗算はmod rで考えているから、計算対象となる自然数の大きさはO(r)である。従って、上の2における1回の乗算の計算量はO~(log r)となる。よって、上の手順で確認するための計算量はO~(log2 n ・ logr)である。
アルゴリズムの正当性の証明の中で示したように、r = O(log5 n) である。従って、高々この回数だけ試行すれば条件を満たす r の値を発見できる。それ故、step 2全体の計算量はO~(log7 n ・ log log5 n) = O~(log7 n)
各a≤rについて、ユークリッドの互除法を用いてO(log min(n, a)) = O(log r)回の整除でGCDを計算できる。各整除はO~(log n)であるから、互除法にかかる時間はO~(log r ・ log n) = O~(log n)である。
これを高々r回繰り返すのであるから、step 3の時間はO~(r・log n) = O~(log6 n) である。
step 4はただ比較するだけである。これは、n, rの各桁を順に比べていけばよいのであるから、n, rの桁数のオーダー、つまりO(log n)である。
合同式における右辺・左辺の多項式を評価するためには、繰り返し二乗法によりO(log n)回の多項式乗算が必要である。ここで、mod Xr+1で考えているのであるから、多項式の次数はO(r)である。また、mod nで考えているのであるから、係数の次数はO(n)である。
一般に、係数がO(c), 次数がO(d)の多項式の乗算1回は、高速フーリエ変換(FFT)を用いればO~(d・log c)の時間が掛かるのであった。従って、この場合はO~(r・log n) = O~(log6 n) である。
FFTの計算量評価については何か適当な計算量理論の教科書を参照のこと。FFTの実装に関しては梅谷武氏のims - 代数 - C++多倍長整数クラスが詳しい。
また、一般には多項式の剰余計算はコストの高いものであるが、ここでは法がXr+1という特殊な形をしているので、これは凖同型Xr |-> -1 により容易に計算できる。つまり、次の要領で多項式の加算に還元できる。
それ故、FFTによる乗算の後、modをとるのに必要な時間はO(r ・log n)である。
この乗算、剰余の計算を、O(√(φ(r)) log n)回繰り返すのであるから、step 5全体の時間は次のようになる。
step 6の時間は明らかに定数時間 O(1) である。
以上を見ると、step 5が最も時間の掛かる計算でありアルゴリズム全体の時間を支配していることが分かる。従って、AKSアルゴリズムの時間的計算量はO(log10.5 n)であるとは言える。
もう一度上の評価を見返してみると、r = O(log5 n) という事実が全体に、特にstep 5に影響していることが分かる。従って、実はstep 2の条件を満たすようなrをもっと小さく取ることができるのだと証明すれば、アルゴリズム全体の計算量評価を改善できる。
（私がきちんと理解していないので）詳しくは述べないが篩理論より、r = O(log3 n)であることは言える。従って、アルゴリズムの計算量はO(log7.5 n)となる。
また、リーマン仮説などの未証明の仮説を認めるのであれば、更にO~(log6 n)まで評価を改善することもできる。