RSA暗号にまつわる個人的にショッキングな出来事

2007-06-13追記::次の段落以後に書いてあることは私の錯覚でした。大変に申し訳ありません。多くの人にコメントを頂戴したこと、ありがたく、感謝申し上げます。私が本屋で立ち読みした内容は、「素因数分解が多項式時間で可能だ」というものではありませんでした。実際には「AKS素数判定法」という多項式時間で素数判定が可能な方式があるのだよ、というお話でした。なお、オーダーについては、えむけいさんがコメントでおっしゃる通りでして、当初、Nの12乗でしたが、その後ずいぶんと改善されているようです。『ていうかその本に素因数分解って書いてたなら眉につば付けて読んだほうがいいです。著者が理解していない可能性が高いので。』(とえむけいさんにご指摘を受けましたが、著者が理解していないのではなくて、私が理解していないのでした。したがって眉唾なのは私の日記の内容です。へこでいます。ショッキングなのは、あれほど平明に書いてある本を誤読した私の頭脳のバカさかげんです。

その解読には自然数の素因数分解が難しいことに依拠しているRSA暗号について、昨日知って個人的にショッキングだったことを。こんなの既に皆さん常識なのかもです・・・私の知識が時代遅れだったのかという意味でもショックでした。

自然数の素因数分解には膨大な計算が必要なのでして、今まで知られている最良のアルゴリズムは、数体ふるい法の一種であり、「準指数的時間」が必要な方式であると、私は信じ込んでいました。　もっとひどいことに、個人的な予想として、「多項式時間」で解けるアルゴリズムなどないだろう、とさえ考えていたのです。

ところが、実際には多項式時間でもって素因数分解できるアルゴリズムがとっくの昔に発見されていたのですね。

気分でいえば、次のような気持ちがしています。厳密な意味では喩えになっていないのですがご勘弁を。

鳥の翼や私たちのプロペラ機では月まで到達できません。　なぜなら、地球と月のあいだには、真空があるからです。　鳥の翼やプロペラでは、空気を使うのですから、月までは飛べないのですよね、必ずや墜落することでしょう。　ところが、天文学者が、地球と月のあいだに十分な濃度の空気が存在していることを発見してしまったのです。さぁ大変。原理的にはプロペラ機でも月に到達できることになったからです。　これからは競争になります。　効率の良い飛行機が編み出されることでしょう。　気球も試されるかもしれません。　あるいはやがてジェット機も試されるでしょう。　少なくとも空気がそこにある限り、私たちは月へ到達できるのですから。　今まであきらめていたことができるようになるかもしれません。　ブレイクスルーがいったん発生したのですから、人間は「これはイケル」と思い、月旅行の方法の開発に殺到するのです。

変な喩えでもうしわけなかったです。ですが、私の感慨は以上のような仮想的な物語でしか表現できません。

さて、これで、素因数分解の困難性をアテにした暗号は、やがて終止符が打たれることになります。　ただし今すぐにではありません。　発見されている多項式時間のアルゴリズムは丁度プロペラ機のようなもので、まだまだ実用には耐えられないからです。　しかしながら、多項式時間のアルゴリズムが存在しないのではないかと、なんとなく考えられていた時代は確かにあったのですから、いまや雲泥の差なのですね。　やがて別の多項式時間のアルゴリズムが次々に発見され、なかには効率の良い、実用的なアルゴリズムが出てくることでしょう。　ジェット機のようなものですね。ひょっとしたら既に発見されていて軍事機密になっている・・としても驚いてはいけないのですよね。

ええと。ここまでは古典的なコンピュータのお話です。

量子コンピュータの場合には、素因数分解が多項式時間でできることが数学的に厳密に証明されているとか。　空気がいらないロケットのようなものですね。