素数

December 2001

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

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

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

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

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

以前は、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では１年です。
＊５：原稿を初めて書いた当時は、（特に日本語では）こういうプロジェクトは少なかったのですが、最近はかなり沢山あるようです。中には、色々とお金がでるものもあるようです。ご興味のある方はこちらなどから探されると良いかも知れません。

各種分散コンピューティングプロジェクトの紹介: プロジェクトや参加のための情報が一覧となっています。
　

（Feburary 2004 update）