山崎愛一 理学研究科准教授 「大きな素数の世界新記録」(2008.11.16)

Filed under: 複眼時評
????????????????????
素数とは、1と自分自身でしか割れない2以上の整数のことです。例えば、2、3は素数ですが、4は2で割れるので素数ではありません。ある整数が素数かどうかは、2から順に割って割り切れるかどうか確かめれば判定できます。例えば23については、2で割ると商が11であまり1、3で割ると7あまり2でともに割りきれません。5で割ると4あまり3で、商が5より小さくなります。23がもし二つの整数の積に分かれるとすれば、小さいほうは5より小さくなければなりません。ですから23は素数だとわかります。一般に整数Nが素数かどうか判定するには、√Nまで割って確かめればいいことになります。

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

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

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

2のn乗から1を引いた形の数をメルセンヌ数と言います。これが素数になるとき、メルセンヌ素数と言います。そのためにはnが素数である必要がありますが、nが素数でも2のn乗マイナス1は素数になるとは限りません。n=2,3,5,7のとき、2のn乗マイナス1はそれぞれ、3、7、31、127となり、すべて素数です。しかしn=11のとき、2の11乗マイナス1すなわち2047は23と89の積になり、素数ではありません。ルカスの判定法と言って、nが素数のとき、2のn乗マイナス1が素数かどうかを判定するための非常に効率的な方法が知られています。

現在メルセンヌ素数は全部で46個知られており、nが小さいほうから順に 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、30402457、32582657、37156667、43112609 です。最後の二つは今年発見されたばっかりで、人類が知っている一千万桁以上の素数はこの二つしかありません。GIMPS(Great Internet Mersenne Prime Search)と言って、世界中の多数のパソコンの空いている時間を利用してみんなでメルセンヌ素数を探そうというグループが発見しました。一番大きな素数は、2008年8月23日に、GIMPSに参加しているカリフォルニア大学ロサンゼルス校のコンピューターが発見しました。これは一千万桁を超す最初の素数の発見なので電子フロンティア財団から10万ドルの賞金が与えられます。大きいほうから2番目の素数は2008年9月6日にHans-Michael Elvenichさんが発見しました。一番大きな素数よりも後のことです。

トップページお問い合わせサイトポリシー著作権について個人情報の取り扱いについて
京都大学新聞社 〒606-8317 京都市左京区吉田本町 京都大学構内 TEL:075-761-2054(直通) 075-753-7531(内線2571) FAX:075-761-6095