1.はじめに


最近発見された世界最大の素数は2^30402457-1(43番目のメルセンヌ素数)で915万桁の大きさがあります。
この世界最大の素数はメルセンヌ素数と通常言われています。
今回は世界最大の素数発見を祝して、メルセンヌ素数について紹介したいと思います。

メルセンヌ(1588-1648)は今で言うメルセンヌ素数について研究していました。
pは素数で、M(p)=2^p-1の形式の素数をメルセンヌ素数と言います。
メルセンヌ素数の探索はGIMPS(The Great Internet Mersenne Prime search)というプロジェクトで
世界的な規模で行われています。
現在迄の探索結果は以下の通りです。

[1]  メルセンヌ素数探索プロジェクト GIMPS:   http://www.mersenne.org/prime.htm



 
No p 桁数 発見年 発見者
1 2 1
2 3 1
3 5 2
4 7 3
5 13 4 1456 anonymous
6 17 6 1588 Cataldi
7 19 6 1588 Cataldi
8 31 10 1772 Euler
9 61 19 1883 Pervushin
10 89 27 1911 Powers
11 107 33 1914 Powers
12 127 39 1876 Lucas
13 521 157 1952 Robinson
14 607 183 1952 Robinson
15 1279 386 1952 Robinson
16 2203 664 1952 Robinson
17 2281 687 1952 Robinson
18 3217 969 1957 Riesel
19 4253 1281 1961 Hurwitz
20 4423 1332 1961 Hurwitz
21 9689 2917 1963 Gillies
22 9941 2993 1963 Gillies
23 11213 3376 1963 Gillies
24 19937 6002 1971 Tuckerman
25 21701 6533 1978 Noll,Nickel
26 23209 6987 1979 Noll
27 44497 13395 1979 Nelson,Slowinski
28 86243 25962 1982 Slowinski
29 110503 33265 1988 Colquitt,Welsh
30 132049 39751 1983 Slowinski
31 216091 65050 1985 Slowinski
32 756839 227832 1992 Slowinski,Gage
33 859433 258716 1994 Slowinski,Gage
34 1257787 378632 1996 Slowinski,Gage
35 1398269 420921 1996 Armengaud,Woltman
36 2976221 895932 1997 Spence,Woltman,(GIMPS)
37 3021377 909526 1998 Clarkson,Woltman,Kurowski,(GIMPS)
38 6972593 2098960 1999 Hajratwala,Woltman, Kurowski,(GIMPS, PrimeNet)
39 13466917 4053946 2001 Cameron,Woltman, Kurowski,(GIMPS, PrimeNet)
40 20996011 6320430 2003 Shafer,Woltman, Kurowski,(GIMPS, PrimeNet)
41 24036583
7235733
2004 Findley, Woltman, Kurowski,(GIMPS, PrimeNet)
42 25964951
7816230
2005 Nowak,Woltman, Kurowski
43 30402457
9152052
2005 Cooper,Boone,Woltman, Kurowski
44 32582657
9808358
2006 Cooper,Boone,Woltman, Kurowski
メルセンヌ素数については色々な予想が有りますが、代表的なものは次の通りです。 (1). メルセンヌ素数は無数に存在するか?   肯定も否定もされていない。 (2). メルセンヌ数で素数でないものは無数に存在するか?    肯定も否定もされていない。    関連した定理を2.理論で採りあげます。 (3). メルセンヌ数で素数でないものは、素数の2乗で割り切れるか?    肯定も否定もされていない。 2.理論 (1). 2^n-1が素数であるためには、nは素数でなければならない。    一般的に a^n-1≡0 mod a-1 であるから a=2,n=n1*n2 とすると    2^n-1≡0 mod 2^n1-1 となるので、2^n-1が素数であるためには、nは素数でなければならない    ことが分かります。 (2). p=4*k+3は素数で2*p+1も素数であるならば、M(p)=2^p-1は2*p+1で割り切れる。    この定理はオイラーによって証明されたものです。    証明は2次剰余の定理を使って行いますが、ここでは2次剰余の定理の説明は省略します。    Q=2*p+1とするとQ≡7 mod 8 となるので2次剰余の定理によって次の式が成り立ちます。    2^p=2^(Q-1)/2≡1 mod Q 従って、p=4*k+3は素数で2*p+1も素数であるならば、2^p-1は2*p+1で割り切れる。    例1 p=11,2*p+1=23だから,M(11)=2^11-1≡0 mod 23 例2 p=23,2*p+1=47だから,M(23)=2^23-1≡0 mod 47 例3 p=83,2*p+1=167だから,M(83)=2^83-1≡0 mod 167 とこんな感じで素数でないメルセンヌ数は見つかるのですが、無数に有るかどうかは分かって    いません。何故なら、p=4*k+3は素数で2*p+1も素数であるようなpが無数にある事を証明できない    からです。    誰でも問題の意味を理解できるのに、誰もその証明をする事ができない所が、数論の面白い所であり    難しい所でもあるのだと思います。 (3). S(0)=4,S(k+1)=S(k)^2-2の数列でS(p-2)≡0 M(p)ならばM(p)は素数である。    この定理はLucas-Lehmerテストと呼ばれており、古くからメルセンヌ素数の探索に利用されて    きました。    証明は省略しますが例を示します。    例 M(7)=2^7-1 の場合 S(0)=4 S(1)=4^2-2=14 mod M(7) S(2)=14^2-2≡67 S(3)=67^2-2≡42    S(4)=42^2-2≡111 S(5)=111^2-2≡0 S(7-2)=S(5)≡0 M(7) だから M(7) は素数である。             Lucas-Lehmerテストのプログラムを作ってみました。      入力するpの値はUbasicの制限上p<4400の範囲内で与えて下さい。      数秒で答えが出ます! 本来、Lucas-Lehmerテストはメルセンヌ数が素数ではないことが分かっても素因数までは      分かりません。そこで今回は小さな素因数を求める処理を追加してみました。 Lucas.ub      10 input "p=";p 20 if p > 4400 then print "p is too big!!":goto 200 30 if p<3 then goto 200 40 M=2^p-1 50 S=4 60 for I=1 to p-2 70 S=(S^2-2)@M 80 next 90 if S=0 then print "M";p;"is Mersenne Prime" 100 :goto 200:else print "M";p; "is not Mersenne Prime" 110 for k=1 to 10000 120 if modpow(2,p,2*k*p+1) = 1 then print "small factor is"; 2*k*p+1:goto 200 130 next 200 end


HOME