Slashdot.jpによると、素数かどうかを多項式時間で判定できるプログラムが開発されたとのこと。ヒデキ指数(検定近し)=250。素晴らしい。生きててよかった。インドというのがまたいい。

素数多項式時間(P)で判定できるかどうかというのは、確か長らく「だめっぽい」という見込みだったはず。暗号がどうこうより、こんなシンプルなアルゴリズム(PDFで見られます)で解けるというのが驚き。このアルゴリズムの途中に「if (r is PRIME)」とあるのは、正当なのだろうか。何だかだまされたような気がしないでもない。と思ったらその後ろにPRIMEのアルゴリズムが書いてあるけど、読み通すのが骨。実装するとどんな感じになるのだろう。