とあるブログ記事への反応（その１）

「異分野の成果があなたの分野の発展に役立った事例はありますか？」というブログ記事にて、科学の基礎研究の必要性・重要性を訴えるための一つの方策として、ある分野の基礎研究成果が後に他の分野の（思いもよらない）発展の礎となった事例が募集されています。
その趣旨には賛同するところですし後で自分でも何か事例を挙げてみようと思うのですが（だから「その１」）、その前に元記事の方が例示しておられた数学（整数論）と暗号分野（RSA暗号）の関連についての以下の記述がどうしても気になるので指摘しておきます。先に事例を挙げてからツッコミを入れる方が行儀の良い態度だとわかってはいるのですが、こちらの方がすぐに書き上がりますので。
（なお、私自身も暗号の専門家というわけではありませんので、もっと詳しい方による「ツッコミへのツッコミ」を歓迎いたします。）

私が感動したのは、RSA暗号のエピソード。数学の整数論という分野において、ある数字Ｘが与えられたとき、それは何の素数（1と自分自身以外では割り切れない数字）を掛け合わせて作られた数なのかを見つける方法（素因数分解）が研究されており、誰が行っても必ず同じ結果がでる方法（機械的な手法）を考えると、既に分かっている素数を使って小さい順にその数字Ｘを割っていくしかないということが分かった。この方法だと、数字Ｘの桁数を変えることで、最新のスーパーコンピューターでも素因数分解するのに1時間〜数億年かかるように調整できることが分かった。

この数学者だけしか楽しめないような事実を基にして、公開鍵暗号の典型例であるRSA暗号という画期的な暗号方式が提案された。このRSA暗号は、発展をとげて、今のインターネット上の買い物を支える基本的な技術となっている。数学の整数論において素因数分解について研究がされていなければ、Amazonやe-Bay、Yahoo Auctionなどは存在しなかった（あるいは、発生が遅れた）ぐらいの技術。

http://d.hatena.ne.jp/next49/20091119/p1

私自身も暗号の専門家というわけではありませんが、後半部分は多分正しいと思います。というか私も「暗号が何に役立っているか」を非専門家の知人に説明する際、よくネットショッピングの例を挙げていますし。

問題は前半部分です。もしある整数を素因数分解するのに

既に分かっている素数を使って小さい順にその数字Ｘを割っていくしかないということが分かった

とすると、それは有名な未解決問題であるP=NP?問題が解決された（クラスPとNPが一致しないことが判明した）ことを意味してしまいます。
P=NP?問題という大仰な代物を持ち出さずとも、例えば「数体篩法」（篩の読みは「ふるい」）と呼ばれる手法のように、「小さい順に素数で割っていく」素朴な手法よりは巧妙かつ桁違いに高速な素因数分解法が実際に発見されています。とはいえ、「数体篩法」をもってしても、現在の標準的なRSA暗号の実装に用いられる整数（例えば1024ビット整数）を素因数分解するにはとてつもなく長い時間を要すると見積もられていますので、

この方法だと、数字Ｘの桁数を変えることで、最新のスーパーコンピューターでも素因数分解するのに1時間〜数億年かかるように調整できる

という箇所だけ見ると間違っていないようにも思えます（詳しい見積もりは憶えていないので、実際には数億年どころの話ではない長い時間がかかる、ということはあるかもしれません）。

しかし、この「数体篩法」（正確にはその改良版が、かもしれませんが）にしても、現在研究者間で広く知られている素因数分解法の中では最速というだけであって、この手法が「理論的に最速」と証明されたわけではありません。いつの日か、「数体篩法」より遥かに高速な画期的手法が発見され、RSA暗号用の巨大整数が現実的な時間で素因数分解可能になり、現在のRSA暗号の安全性が損なわれる事態が起こる可能性も理論的には（今のところ）否定できないのです。
勿論、現時点ではそのような画期的手法は未だ人類の知るところでないという仮定が専門者間で広く信じられています。だからこそRSA暗号に基づく暗号通信技術がこれだけ実用に供されているわけですが、理論的に証明されたわけでない以上、その「仮定」が本当に正しいかどうか常に検証を続けていく必要があります（「仮定」が理論的に証明できればそれに越したことはありませんが）。

現在も数学者や暗号研究者は（ある人はRSA暗号の安全性検証のため、またある人は純粋な好奇心から）より高速な素因数分解法の開発に日夜取り組んでいます。そして、現代社会で用いられているRSA暗号の実装（特に整数のサイズ）は、これら最先端の研究成果の推移を元に決定され、また改良の必要の有無が検討されてきました。
今日の情報化社会の安全性基盤は、素因数分解という「何の役に立つのかわからない」基礎研究の成果によって支えられているのです。

なお、理論的に証明されていない「仮定」にRSA暗号の安全性が基づいているという話をすると、じゃあそんな危ないものを実用化なんてするなよ、というツッコミを受けるかもしれませんので（私の知識の範囲で）一応補足しておきます。
かつて、暗号が学問の対象になり始めた頃は、暗号関係の研究会で提案した暗号方式がその場で（！）解読方法を指摘されることがあるなど、（現在の視点では）充分でない安全性検証により提案される暗号方式も少なくなかったそうです。その反省から、近年の暗号分野では「証明可能安全性」という概念が提唱され、多くの暗号方式が理論的な安全性検証を添えた形で提案されるようになりました。RSA暗号も（ある意味で）この「証明可能安全性」を備えた暗号方式です（追記：ただし、実はRSA暗号の安全性と素因数分解の関係は微妙なもので、説明が大変なため「ある意味で」ともやもやした書き方になっています。）。
しかし、数学における公理系や物理学における物理法則と同様、暗号の安全性証明においても論証の元となる何らかの「前提」が必要です。勿論この「前提」は何でも良いわけではなく、充分に信じられる「前提」であることが求められます。RSA暗号の場合、その「前提」は（平たく言うと）「素因数分解はとても難しい」ということであり、「素因数分解がとても難しい」限りにおいてはRSA暗号の安全性は理論的に証明されています。（より正確には、一口に暗号の「安全性」といっても色々な種類があり、RSA暗号はそのうちの一つの種類の「安全性」を満たしています。）この「前提」は古典力学や量子力学のような物理法則ほど確かなものではないかもしれませんが、素数の発見以降二千年近くにわたり研究が行われてきたにもかかわらず未だ素因数分解の効率的手法が発見されていないという歴史的事実により、少なくとも今日の情報化社会を委ねられる程度には専門家の間で信頼されている「前提」です。
つまり、現在の情報化社会の安全性基盤は、素因数分解に関する長い研究の歴史それ自体の上に成り立っていると言えるのです。「継続は力なり」と言いますが、基礎研究を継続して行うことが強固な社会基盤の確立に繋がっている一つの実例であると思います。
（ちなみに物理法則と同等に確かな「前提」に基づく暗号技術としては所謂「量子暗号」（量子鍵配送）がありますが、これも量子力学という物理学の研究成果が暗号という全く別の分野に貢献した例と言えましょう。）