素数判定

素数判定が多項式時間で行えると数年前に証明されていたことをさっき知った。

インド工科大の教授・学生の名前から AKS アルゴリズムと呼ばれるらしい（Manindra Agrawal教授、学生のNitin SaxenaとNeeraj Kayal）。 PRIMES is in P という題で公開された論文は数ページしかなく内容も簡単だとか。

昨今の暗号・セキュリティ業界では素数は大活躍。素数を作るには， 適当に整数を作りそれが素数かどうか調べるということになるわけですが、 既存の素数判定法は大体次の3種類のいずれかでした。

1. 確率的な方法（→実用上は問題無いらしいが、確率的なので素数でないかもしれない）
2. （準）指数時間かかる（→実用的ではない）
3. 他の（まだ証明されていない）理論に依存している

というわけで、他の理論に依存しない多項式時間のアルゴリズムが見付かったというのは速くて確実な素数判定ができるので凄いことなのだとか。以下に論文と日本語の解説をリンクしておこう。後で読む（何

• PRIMES is in P 初版のPDF
• PRIMES is in P 第6版のPDF
• 多項式時間素数判定アルゴリズムについて
• AKSアルゴリズム
• AKS素数判定法 – Wikipedia

でも多項式時間とはいえ O(log^10.5n) らしい（最近は改良されて O(log^7.5n) までは落ちるらしい）ので、いまでも確率的な方法が使われている。

しかし、論文出たのが2002年か。さっぱり知らなかった。アルゴリズムに興味持ったのなんてここ数年のことだしなあ。