複眼時評

素数とは、１と自分自身でしか割れない２以上の整数のことです。例えば、２、３は素数ですが、４は２で割れるので素数ではありません。ある整数が素数かどうかは、２から順に割って割り切れるかどうか確かめれば判定できます。例えば２３については、２で割ると商が１１であまり１、３で割ると７あまり２でともに割りきれません。５で割ると４あまり３で、商が５より小さくなります。２３がもし二つの整数の積に分かれるとすれば、小さいほうは５より小さくなければなりません。ですから２３は素数だとわかります。一般に整数Ｎが素数かどうか判定するには、√Ｎまで割って確かめればいいことになります。

ところで、Ｎが非常に大きな数の場合はどうすればいいでしょうか。Ｎが２０桁のときは、１０桁までの素数で順に割れば素数かどうか判定できます。それは最新型のパソコンを使えば数分でできます。しかしＮが５０桁になると、２５桁までの素数で割る必要があり、少なく見積もっても１台のパソコンでは何億年もかかることになります。でも世界中のコンピューターを総動員して、たくさんで手分けして割り算していけばもしかしたら何とか数年ぐらいでできるのかもしれません。Ｎが６０桁になると、３０桁までの素数で割る必要があり、世界中のコンピュータを使ってもとてもできそうにありません。

ところが、√Ｎまで割り算しなくてもＮが素数かどうか判定する方法が１９８０年にAdleman、Pomerance、Rumelyにより発明されました。百桁程度の整数が素数かどうかが、当時の大型計算機で４０秒以内で判定できました。現在では一台のパソコンで数秒でできます。その後、楕円曲線という曲線を使ったより高速な方法が発明されました。この方法はＥＣＰＰ（楕円曲線素数判定法）と呼ばれます。三百桁程度であれば、一台のパソコンで一分かからないぐらいで判定できます。しかしこのＥＣＰＰでも一万桁程度の整数が素数かどうか判定しようとすると複数のコンピューターを数ヶ月間走らせ続けないといけないぐらい大変な計算になってしまいます。

このように、非常に大きな整数が素数かどうか判定するのはコンピューターを用いても難しいのです。そこで、特別な形の整数だけがずっと先の方まで調べられています。

２のｎ乗から１を引いた形の数をメルセンヌ数と言います。これが素数になるとき、メルセンヌ素数と言います。そのためにはｎが素数である必要がありますが、ｎが素数でも２のｎ乗マイナス１は素数になるとは限りません。ｎ＝２，３，５，７のとき、２のｎ乗マイナス１はそれぞれ、３、７、３１、１２７となり、すべて素数です。しかしｎ＝１１のとき、２の１１乗マイナス１すなわち２０４７は２３と８９の積になり、素数ではありません。ルカスの判定法と言って、ｎが素数のとき、２のｎ乗マイナス１が素数かどうかを判定するための非常に効率的な方法が知られています。

現在メルセンヌ素数は全部で４６個知られており、ｎが小さいほうから順に 2、3、 5、 7、 13、 17、 19、31、61、89、107、 127、521、607、1279、 2203、2281、 3217、 4253、4423、9689、9941、11213、19937、21701、23209、 44497、 86243、110503、132049、216091、 756839、 859433、1257787、1398269、2976221、3021377、6972593、13466917、20996011、24036583、25964951、３0402457、32582657、37156667、43112609 です。最後の二つは今年発見されたばっかりで、人類が知っている一千万桁以上の素数はこの二つしかありません。ＧＩＭＰＳ（Great Internet Mersenne Prime Search）と言って、世界中の多数のパソコンの空いている時間を利用してみんなでメルセンヌ素数を探そうというグループが発見しました。一番大きな素数は、２００８年８月２３日に、ＧＩＭＰＳに参加しているカリフォルニア大学ロサンゼルス校のコンピューターが発見しました。これは一千万桁を超す最初の素数の発見なので電子フロンティア財団から１０万ドルの賞金が与えられます。大きいほうから２番目の素数は２００８年９月６日にHans-Michael Elvenichさんが発見しました。一番大きな素数よりも後のことです。