[アルゴリズム] 素数判定アルゴリズムの複雑性
1-2時限目はアルゴリズム論。O 教官と素数判定アルゴリズムの複雑性について話をしました。話題の中心は Primes is in P という論文に書かれている AKS アルゴリズムについてで、このアルゴリズムは私と O 教官が共に興味を持っているものです。
何がすごいって、素数判定が多項式時間以内にできてしまうんですよ。普通、素数判定というと 2〜√n までの数でしらみつぶしに割っていくイメージですが、これだと指数関数時間以内じゃないと解けないんですね。つまり、入力桁数 N に対する時間計算量が O(e^N) だとということです。
これに対して、AKS アルゴリズムの時間計算量は O(N^12)。つまり明らかに高速になります。そのアルゴリズムがまたエレガントで、いつ見ても美しいと思います。
