かおすもにゅめんたむ

独自な視点でアニメ・声優・ゲーム・アイドルなどを考察するブログ

f:id:mochirixi:20181004170142j:plain f:id:mochirixi:20180920170704j:plain f:id:mochirixi:20180920170713j:plain f:id:mochirixi:20180920170646j:plain

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

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

www.mersenne.org

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

 

スポンサードリンク

 

メルセンヌ数とは

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

 M= 2n − 1

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

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

M= Mpq = 2pq-1 = (2p-1)(2p(q-1)+2p(q-2)+・・・+1)となりMn素数ということに矛盾するからである。(背理法)

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

例えばn = 67のとき

M= 267-1 = 147,573,952,589,676,412,927

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

 

素数判定法(リュカ-レーマーテスト)

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

nが奇素数のとき、メルセンヌ数 M= 2n-1 が素数となるための必要十分条件は、S0 = 4, Sp = Sp−12 − 2 (p ≧ 1) と定義したときに Sn-2 が Mn で割り切れることである

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

リュカ–レーマー・テストの証明 - Wikipedia

実際に試してみよう。

n = 3のときM= 23-1 = 7

S= S02-2 = 42-2 = 14

確かに7で割り切れる。

n = 5のときM= 25-1 = 31

S= S12-2 = 194

S= S32-2 = 37634

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

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

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

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

Lucas–Lehmer primality test - Wikipedia

 

 

まとめ

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

www.mirikai.site