暗号と素数
（この記事は「もっと辺境から戯れ言」に投稿した記事です）
『SoftwareDesign』2003年11月号のすずきひろのぶさんの記事の HTML ドキュメントを見つけましたので紹介します。
この中で 「昨年、3人のインドの数学者が計算量のオーダーが多項式時間の決定性素数判定を開発し」 とありますが， これは「AKS アルゴリズム」と呼ばれているものです。 「計算機暗号屋日記」 1/22 の記事で AKS アルゴリズムを日本語で解説しているページが紹介されていましたので， こちらでも紹介しておきます。
AKS アルゴリズムについてはリンク集もあるのですが， 日本がイラク戦争に賛同を表明してしまったため， 日本からは閲覧できなくなっています。（こんなところにもイラク戦争の影響があるんですねぇ） 日本語の情報としては「素因数分解工房」のリンク集ページが参考になるでしょうか。
「CRYPTO2003 レポート」 で他に気になる点といえば RC4_MD5 を使った SSL/TLS へのダメ出しでしょうか。 Web のみならずメール送受信や VPN などでも SSL が使われはじめているので， この辺の話は気になるところです。
現代の暗号技術にとって「素数」は重要な要素になっています。 そこで大きな桁の「素数」をいかに効率良く見つけ出すかが鍵となります。 PGP/GnuPG では「楕円曲線素数判定法（ECPP）」が使われているようです。 IPA/ISEC では暗号技術として使われる素数判定法をいくつか紹介しています。
また分散コンピューティング・プロジェクトとしてできるだけ大きな素数を探すプロジェクトも存在します。 昨年末に「Great Internet Mersenne Prime Search（GIMPS）」というプロジェクトで過去最大桁数の素数が発見されたニュースは大きく取り上げられたのでご存じの方もいるかもしれません。
- 史上最大のメルセンヌ素数、分散コンピューティングプロジェクトで発見
- 分散コンピューティングで栄誉ある大発見を
- GIMPS 世界最大の素数を求め続ける分散コンピューティングプロジェクト （日本語による GIMPS 情報サイト）
「メルセンヌ素数」というのはメルセンヌ数という特殊なルールで導かれる数のうち素数の性質を持っているものです。 全ての数に対して素数であるかどうかを探すのは効率が悪いため， 「メルセンヌ素数」のような特殊な数から調べているのです。 また「メルセンヌ素数」に対しては効率的な素数判定法（Lucas-Lehmer 判定法）が存在しているため探索が比較的容易であることも理由のひとつです。 （それでも膨大な計算量が必要ですが）
日本発の素数探索プロジェクトも存在します。
- 素数探索プロジェクト （徳島大学工学部知能情報工学科・森井研究室）
このプロジェクトでは100万桁以上の「一般化フェルマー素数」を探しています。 素数判定には Proth 判定法を使っているようです。
「メルセンヌ素数」「一般化フェルマー素数」「Lucas-Lehmer 判定法」「Proth 判定法」については以下のコンテンツが参考になります。