千万桁の素数
いやぁ， 最近この手の話題に疎くて。 遂に1300万桁の素数が発見されたようです。 元ネタはこちら。
- UCLA mathematicians discover a 13-million-digit prime number
- 243112609-1 is prime （実際にどんな値かここで見ることができます）
実は， 1000万桁以上の素数には EFF （Electronic Frontier Foundation； 電子フロンティア財団）から10万ドルの賞金がかけられていて， 今回の素数を発見したカリフォルニア大学ロサンゼルス校（UCLA）の数学者達は， その栄誉と賞金を手にしたわけです。 （実際には， その方々が賞金の全てを受け取るわけではないようですが）
今回の発見は GIMPS （Great Internet Mersenne Prime Search）プロジェクトによる成果でもあります。 GIMPS は分散コンピューティング・プロジェクトのひとつで， インターネットに繋がるたくさんのパソコンの空き CPU 時間を利用して大きな計算問題を解いていきます。 素数および GIMPS については2004年の記事で言及していますが， 以下に（一部編集して）再掲載しておきます。 ご参考までに。
現代の暗号技術にとって「素数」は重要な要素になっています。 そこで大きな桁の「素数」をいかに効率良く見つけ出すかが鍵となります。 PGP/GnuPG では「楕円曲線素数判定法（ECPP）」が使われているようです。 IPA/ISEC では暗号技術として使われる素数判定法をいくつか紹介しています。
また分散コンピューティング・プロジェクトとしてできるだけ大きな素数を探すプロジェクトも存在します。 昨年末（注：2003年12月）に「Great Internet Mersenne Prime Search （GIMPS）」というプロジェクトで過去最大桁数の素数が発見されたニュースは大きく取り上げられたのでご存じの方もいるかもしれません。 （注：その後， 2005年にも GIMPS によって915万桁のメルセンヌ素数が発見されています。 惜しかったですね）
- 史上最大のメルセンヌ素数、分散コンピューティングプロジェクトで発見
- 分散コンピューティングで栄誉ある大発見を
- GIMPS 世界最大の素数を求め続ける分散コンピューティングプロジェクト （日本語による GIMPS 情報サイト）
「メルセンヌ素数」というのはメルセンヌ数という特殊なルールで導かれる数のうち素数の性質を持っているものです。 全ての数に対して素数であるかどうかを探すのは効率が悪いため， 「メルセンヌ素数」のような特殊な数から調べているのです。 また「メルセンヌ素数」に対しては効率的な素数判定法（Lucas-Lehmer 判定法）が存在しているため探索が比較的容易であることも理由のひとつです。 （それでも膨大な計算量が必要ですが）
「メルセンヌ素数」「Lucas-Lehmer 判定法」については以下のコンテンツが参考になります。