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

2018年1月3日にGIMPS(Great Internet Mersenne Prime Search)が史上最大の素数を発見し、その記録が更新されたことが発表された。

その素数は2^77,232,917-1であり、50番目のメルセンヌ素数である。メルセンヌ数は史上最大の素数の発見に不可欠なものであり、史上最大の素数の更新はメルセンヌ素数以外には、現状不可能とも言ってもいい。ではなぜメルセンヌ素数が巨大な素数の発見に都合がいいのだろうか。

スポンサードリンク

メルセンヌ数とは以下のような定義で表される数である。

M_n= 2ⁿ − 1

つまり2の冪乗から1を引いた数だ。とても分かりやすい。

M_nが素数だとするとnは素数である。なぜならばnがpで割り切れるとすると

M_n= M_pq= 2^pq-1 = (2^p-1)(2^p(q-1)+2^p(q-2)+･･･+1)となりM_nが素数ということに矛盾するからである。(背理法)

しかしながらnが素数のときM_nが素数とは限らない。

例えばn = 67のとき

M_n= 2⁶⁷-1 = 147,573,952,589,676,412,927

これは193,707,721と761,838,257,287の積である。

nが素数のときでもM_nが素数でないなら素数を見つけるのが大変なことには変わりないのではないかと思うかもしれない。しかしメルセンヌ数に関しては、素数であるかどうかを判定するのに比較的簡便な方法が存在する。それをリュカ-レーマーテストと呼ぶ。

nが奇素数のとき、メルセンヌ数 M_n= 2ⁿ-1 が素数となるための必要十分条件は、S₀ = 4, S_p = S_p−1² − 2 (p ≧ 1) と定義したときに S_n-2 が M_n で割り切れることである

リュカ-レーマーテストの証明は長くなるので割愛する。気になった人はwikipediaに詳しく書かれているので参考にしてほしい。

実際に試してみよう。

n = 3のときM_n= 2³-1 = 7

S₁= S₀²-2 = 4²-2 = 14

確かに7で割り切れる。

n = 5のときM_n= 2⁵-1 = 31

S₂= S₁²-2 = 194

S₃= S₃²-2 = 37634

37634は31*1214でちゃんと割り切れている。

これを用いればいちいち素因数分解することなく素数であるかどうかを判定できる。素因数分解は既存のコンピュータで行うのは時間がかかりすぎるが、この方法を用いれば、S_n-2を求めて、それがM_nで割り切れるかどうかを調べるだけで素数かどうかがわかる。

実際に今回の発見された素数について、素数かどうかを判定するのには6日間しか掛かっていない。

n = 11の場合は、M_n = 2047でこれは素数ではない(23と89の積)のだが、S₉ が割り切れないことを示そうかと思ったが、流石に長くなるので止めておく。実際は剰余関数を用いて判定する。詳しくは英語版Wikipediaを参照してほしい。

巨大素数は良い性能のパソコンさえあれば実は誰でも発見できる。今回も発見したのはGIMPSに参加しているボランティアの人だ。素数を探す旅に出るのも楽しいかもしれない。

かおすもにゅめんたむ