史上最大の素数の発見－メルセンヌ素数とは－

史上最大の素数の発見

先日、歴史上最大の素数が米セントラルミズーリ大学で発見されたと報道がありました。カーティス・クーパー教授のグループが発見したもので、なんと2233万桁もの巨大な素数でした。$２^n－１$で表される数をメルセンヌ数と言われていますが、この$n=74207281$の場合が、素数であると判定されました。
クーパー教授は、PCをつなげて素数を探すプロジェクトであるGIMPS(The Great Internet Mersenne Prime Search) のメンバーで今回は800台のPCをつないで見つけたということです。これまでの最大の素数は、同じクーパー教授が$2013$年にみつけた$n=57885161で1742万桁$でしたから、大幅に記録を伸ばしたことになります。今回の素数をA4の紙に書くと1万枚にも上るそうです。

メルセンヌ数とは

今回見つけられた素数は、メルセンヌ数といわれるもので、$M_n=2^n－1$で表されるものです。メルセンヌは17世紀の修道士で多くの数学者と親交があったと言われています。メルセンヌは、$a^n－1(nは自然数)$という形の数を考えています。ただし、$a>2ならa^n－1＝(a-1)(a^{n-1}+･････+1)$となりますから、必ず合成数（つまり素数ではありません）となります。そこで、メルセンヌは、$a=2$の場合を考え、メルセンヌ数$M_n=2^n－1$が、どんな$n$のときに素数になるのかを調べていったのです。いくつか計算してみると、
$M_1＝1$
$M_2＝3：素数$
$M_3＝7：素数$
$M_4=15：合成数$
$M_5＝31:素数$
$M_6=63:合成数$
$M_7＝127:素数$
などとなります。もし$n$が合成数なら、$M_n$も合成数になる事は容易に示すことはできますが、$M_{11}＝2047＝23ｘ89$で合成数となり、$n$が素数であっても必ずしもメルセンヌ数が素数になるとはいえません。それでは、そのような$n$のときに、$M_n$が素数になるのでしょうか。

メルセンヌの計算

メルセンヌは、相当な計算をしたと思われますが、$257$までの$n$のうち、$M_n$が素数になるのは、$n＝2,3,5,7,13,17,19,31,67,127,257$のときであると主張しています。ただし後の検討により$n＝67,257$は素数ではないことが確かめられています。$n=31$の場合は、オイラーが素数であると確かめています。$M_{257}＝231584127847463239084714197001737581570653996993312811915$$16801582659279871$ですから、素数か合成数かの判定もたいへんです。

リュカテスト・リュカレーマーテスト

リュカによって1891年に素数判定法が発見されました。クーパー教授の素数判定も基本的にリュカテストによっています。
リュカは、リュカテストを発見して$M_{127}$の素数判定をしています。リュカテストの必要十分性の証明はかなり難しいですので、興味がある方は調べてみてください。

簡単のために、$M_7=2^7－1＝127$が素数であることを確かめてみましょう。
リュカテストは、$a_1=4$からはじめて、$(modM_n)$で2乗しては、２を引くと言う操作を続けます。$a_{n-1}$まで計算し、$a_{n-1}≡0 (mod M_n)$なら、$M_n$は素数です。そうでなければ合成数となります。実際に$M_7=127$でやってみましょう。

$a_1＝4$
$a_2=4^2－2≡14 (mod 127)$
$a_3＝14^2－2≡67(mod 127)$
$a_4=67^2－２≡42(mod 127$
$a_5＝42^2ー2≡111(mod 127)$
$a_6＝111^2ー2≡0(mod 127)$
となりますから、$M_7＝127$が素数である事が確かめられました。

クーパー教授の今回のメルセンヌ数は、$n=74207281$の場合ですから、ものすごい計算量が必要だと言う言う事がよく分かります。素数は暗号にも使われておりますし、現代のＩＴ社会にはなくてはならないものだと思います。