素数

December 2001               
February 2004 updated   

子供と算数の話をしていたときにふと素数の話になりました。そのちょっと前に「フェルマーの最終定理」なる数学の物語を読んでいたからかもしれません。その本の中には、素数にまつわるお話もいろいろとかかれてあったからです。

素数（２，３，５，７，１１，１３・・・）は、実生活の中でまったく縁のない数学の中だけの言葉のように感じている人もおおいかもしれません。要するに１とその数自身以外に約数のない数字と言う意味の数なのですが、実はネットワークに重要な役割を演じています。そして、あなたも知らぬ間に使っているかもしれません。

RSAという暗号方式を聞いたことがあるでしょうか？インターネット上でほぼ標準として使われている一つの暗号方式の名前です。インターネットエクスプローラーなどのブラウザには、この技術がバンドルされています。この暗号方式に欠かせないのが素数なのです。（RSAの概要参照）学校を卒業して社会人となってから、素数とか素因数分解なんて無縁のものと思っていませんでしたか？文化系の大学生でもほとんど学校ではお目にかかりませんよね。でも、パソコンの前に座って、インターネット経由で暗号化された通信、例えば、クレジットカード番号を入力して送信するとき等にこの暗号方式が使われていることがあるのです。

子供とは、こんな難しい話はしません。ただ、どうやって素数を求めるか？のお話をしていたのです。小学校か中学校の教科書に書いてあったと思うのですが、１つは エラストテネスの篩いという、表を書いて倍数を順番に消していく方法、もうひとつはパソコンならではの実際に数字を割ってみて虱潰しに確認する方法です。

最初の方法では、１００まで程の１０ｘ１０の表を作って、鉛筆で数字を消していきました。もう一つの方法では、素数かどうか確認したい数字の平方根（ルート）までを計算すれば良いことを教えて確認しました。子供とは、ここまでだったのですが、ふと今これを書いているパソコンでどのくらいのスピードで素数を見つけることができるか知りたくなりました。むらむらとこんな欲求が訪れるとどうしても止まらない性格は、子供そっちのけでコーディングを始めることに・・・。

以前は、VBやC、C++、JAVAなどで遊ぶこともあったのですが、最近は全く時間がなくこれらのコンパイラーもアップデートされておらず（Winで走るJAVA以外は）使うこともでない状態であったので、手近にあったエクセルのVBAを使うことにしました。ごちゃごちゃとやって数時間後、こんなものに仕上がりました。（Prime.xls）

最初、５万までの素数を見つけ、表示するのに１６秒ほどかかったものが、最終版では１０００万までの検索範囲で１０秒もかからずにできるようになりました。この結果にちょっとした、軽いショックを受けました。どう考えても人生をかけてこの計算をしてもやり終えられないのに、目の前のパソコンが１０秒かけずに終わらしたのです。１００年カレンダーが死ぬ日が記載されているため自殺者を誘発すると言う話を聞いたことがありますが、それに似た人間の無力感を感じさせられました。頭では、判っていても、目の前で起こるとまた別の感覚が訪れます。　

おまけ：
今までに見つかった（確認された）最大の素数は、約６３２万桁の数　2^20,996,011-1と思われます。 （２００３年末現在）この素数はメルセンヌ素数と言われる数字で、（たぶん）第４０番目の2^ｎ-1で表される素数です。（たぶんと書いたのは、この数までの全ての数字がまだ確認されていないからです。）分散コンピューティングのプロジェクト（GIMPS）で見つかったこの数字は、このプロジェクトで全体で １３テラFLOPS程度の実行速度^*1 で計算され、１００万超^*2 におよぶ候補の数から拾い上げられたたったひとつの数字です。このプロジェクトでは、 同様にこの分散コンピューティングのシステムを使用して、暗号解読コンテストを共同で挑戦しています。また、このプロジェクトでは、このメルセンヌ素数を探索するために各CPUで最適化されたプログラムが配布されています。そのプログラムによるCPU毎のベンチマークの一覧表があります。これをみると最適なコードでかかれたときの各CPUの能力差が判ります。

一方、暗号解読を専門にやっているdistributed.netでは、さらなる分散コンピューティングの 計算パワーがあるようです。^*3 ところでこれだけのパワーをかけて求められたメルセンヌ素数は、有効性の判らない意味のある数字として最大のものと言われているようです。（実際は、このメルセンヌ素数から計算される完全数の方が大きい数になります。笑）その一方で、メルセンヌ素数（または、完全数）の発見には賞金がかけられています。直近の賞金が出るメルセンヌ数は、１０００万桁以上のメルセンヌ素数を最初に発見した人またはグループというものです。GIMPSのルールによれば、もしあなたがこのプロジェクトに参加して、１０００万桁以上のメルセンヌ素数を見つけると＄５００００がもらえます。（ただし、P4-２GHzのマシンで １０００万桁の１つの数字を確認するのに約２ヶ月かかり^*4、確率は約２５万分の１だそうです。）もっと大きなメルセンヌ素数を見つけるともっと高額の賞金が貰えますが、現実的に今のコンピューターレベルでは難しいようです。ちなみに第３９番目 と４０番目のメルセンヌ素数を見つけた人には、それぞれ＄５０００の賞金が、１０００万桁以上のメルセンヌ素数がこのプロジェクトで見つけられたときに 、その賞金から分与されます。まあ、賞金よりは、ピタゴラス、オイラー、ガロアなどと並んで（？）X番目のメルセンヌ素数を見つけた人として、数学史に隅っこに名前が残ることの方が、大きなことのように思います。これは、人類の歴史が続く限り、変わらない出来事（史実）となりますから。^*5

＊１：２００１年末では、２TFLOPS程度でした。
＊２：指数部分が6,520,000〜25,350,000の範囲の候補が106万個ほどあります。
＊３：2004.2現在では日本語ページのみ古い実効速度が載っていますが、統計のページ（リンク切れ等不調が多いようです）や他言語のページから全体でのスピードをFLOPS表記されるものが無くなっています。2001年末頃には、１０T FLOPS以上との記載がありました。
＊４：P3-500MHzでは１年です。
＊５：原稿を初めて書いた当時は、（特に日本語では）こういうプロジェクトは少なかったのですが、最近はかなり沢山あるようです。中には、色々とお金がでるものもあるようです。ご興味のある方はこちらなどから探されると良いかも知れません。