« ブッシュは宇宙開発を止めたがっている? | メイン | teikade 最終バージョン »

暗号と素数

(この記事は「もっと辺境から戯れ言」に投稿した記事です)

『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)」というプロジェクトで過去最大桁数の素数が発見されたニュースは大きく取り上げられたのでご存じの方もいるかもしれません。

「メルセンヌ素数」というのはメルセンヌ数という特殊なルールで導かれる数のうち素数の性質を持っているものです。 全ての数に対して素数であるかどうかを探すのは効率が悪いため, 「メルセンヌ素数」のような特殊な数から調べているのです。 また「メルセンヌ素数」に対しては効率的な素数判定法(Lucas-Lehmer 判定法)が存在しているため探索が比較的容易であることも理由のひとつです。 (それでも膨大な計算量が必要ですが)

日本発の素数探索プロジェクトも存在します。

このプロジェクトでは100万桁以上の「一般化フェルマー素数」を探しています。 素数判定には Proth 判定法を使っているようです。

「メルセンヌ素数」「一般化フェルマー素数」「Lucas-Lehmer 判定法」「Proth 判定法」については以下のコンテンツが参考になります。

Tags:
2004-01-22T12:41:36+09:00 Spiegel (licensed) [暗号・セキュリティ] このエントリーを含むはてなブックマーク

トラックバック

現在 spam 対策のため Trackback Auto Discovery を無効にしています。 あしからずご了承ください。

トラックバック URL:

コメント