いろいろ見ていた中で拾ったネタです。21世紀ももう７年が過ぎましたのですが、

21世紀における科学の達成は？

と大上段に構えた問いをすると、「ポアンカレ予想」の解決とかいろいろありますけど、コンピュータと密接に関連するもので実はこんなのがあるのです。

決定的でかつ多項式時間で終わる素数判定法

が、2002年に出ています。これを発見したのはインド工科大学の Agarwal 教授と２人の学生による、AKS素数判定法というやり方です。まあ、素数判定法というと、いわゆる「フェルマーテスト」と、そのウラを掻いてしまう合成数をなくす改善をした、ミラー・ラビン判定法があって、これらは簡単に実装できるので、暗号ライブラリなどでよく使われているわけです。

しかし、フェルマーテストやミラー・ラビン判定法は、「確率的」な判定法です。言い換えると、「１００％ではないが、独立に試行できる判定法を繰り返し適用することで、合成数が返ることを極めて低い確率にできるアルゴリズム」のわけです。まあ、勿論これで実用上は問題がないわけですね。

しかし、「確率的ではなく、決定的なやり方で、しかも本当に素因数分解するようなやり方ではない」やり方があるのだろうか....という謎に解決がついた、ということなんですね。まあ、計算量理論の上では、「Ｐ問題」と「ＮＰ問題」というような言い方で区別するわけですが、このAKS判定法によって、

決定論的な素数判定は、Ｐ問題である

ということになった、というのが非常に興味深いところです。このやり方は私が理解する範囲だと、「チェックすべき範囲を有効に制限でき、その範囲でのチェックが通ることが、素数である必要十分条件だ」ということが証明できる、ということのようです。

とはいえ、実際にこのアルゴリズムを適用するには、やはりステップがかかり過ぎる、というのがあって、必ずしも既存の確率的素数判定法を駆逐する、というわけにはいかないようですが、それでも、

素数判定が本質的に「やさしい」（実際には時間がかかるのですが）問題だ

ということが厳密に証明された、というのは面白いことです。で、やはり更に興味深いのは...やはり「インド」というあたりでしょうか。「未来のＩＴ大国？」などと注目されるインドですが、やはり神秘の人ラマヌジャンの国でもあり、もう少し身近なあたりだと、ドラゴンブック（そういえば洋書では第２版が出てますね...メチャ高いんでびっくりしますけど）の Ravi Sethi がやはりインド出身だったりします。Ravi Sethi だって、その名のついた「Sethi - Ullman数」で有名なわけですし....というわけで、「インドの神秘」というのを、何か個人的に印象強く感じます。