メルセンヌ数

提供: miniwiki
移動先:案内検索

メルセンヌ数(メルセンヌすう、: Mersenne number)とは、2の冪よりも 1 小さい自然数、すなわち 2n − 1n は自然数)の形の自然数のことである。これを Mn で表すことが多い。2進数表記では、n 桁の 11⋯11 となる。

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, …オンライン整数列大辞典の数列 A000225から初項 0 を除いたもの。太字素数、素数を除いたメルセンヌ数はオンライン整数列大辞典の数列 A135972を参照)

Mn = 2n − 1 が素数ならば n もまた素数であるが、逆は成立しない (M11 = 2047 = 23 × 89)。素数であるメルセンヌ数をメルセンヌ素数(メルセンヌそすう、: Mersenne prime)という。

なお、「メルセンヌ数」という語で、n が素数であるもののみを指したり[1]、さらに狭くメルセンヌ素数を指す場合もある[注釈 1]

基本的な性質

Mn が素数ならば n もまた素数であることは、次の式から分かる[2][3]

2ab − 1 = (2a − 1)(1 + 2a + 22a + ⋯ + 2(b−1)a).

対偶命題n が合成数ならば Mn は合成数である」が示される。また、この等式より、m | n のとき Mm | Mn である。

しかし、逆に p が素数でも Mp が素数とは限らない(最小の反例:M11 = 2047 = 23 × 89)。そのため、数が大きくなるにつれ直接素因数分解を試みるのでなく、間接的に素数であるかないかを判定する素数判定法が考案された。これが後述するエドゥアール・リュカによる判定法(リュカ・テストEnglish版)と、それを改良し今日使われているデリック・ヘンリー・レーマーEnglish版による判定法(リュカ–レーマー・テストEnglish版)である。

完全数

Mp = 2p − 1 が素数ならば、2p−1(2p − 1)完全数である[2][4]。この定理はすでに紀元前3世紀頃のユークリッド原論で証明されていた[5]。したがって、完全数の探索はメルセンヌ素数の探索に終始された。

2p−1(2p − 1) は明らかに偶数であるが、偶数の完全数でこの生成式から得られるもの以外はないのか2000年間にわたって未解決であったが、18世紀オイラーによりこの形に限ることが証明された[4]

メルセンヌ数の素因数

p を素数とする。

  • Mp の素因数は 2p を法として 1 と合同[6]、かつ 8 を法として 1 または −1 と合同である[7]
  • p ≡ 3 (mod 4) のとき、Mp2p + 1 で割れることと、2p + 1 が素数であることは同値である[7]
  • Mp の最大素因数を q とすると、qc5 p log pc5 は計算可能な定数)(Erdős–Shoreyの定理1)[8]

メルセンヌ素数

メルセンヌ素数(メルセンヌそすう、Mersenne prime)とは、素数であるメルセンヌ数のことである。

2018年1月現在知られている最大のメルセンヌ素数は、2017年12月に発見された、それまでに分かっている中で50番目のメルセンヌ素数 277232917 − 1 であり、十進法で表記したときの桁数は2324万9425桁[9]に及ぶ。

メルセンヌ素数の発見の歴史

紀元前3世紀頃のユークリッド原論において知られる完全数の生成式で見出されている[5]。そこから素数であるメルセンヌ数を見つけることこそが完全数を見つけることとなった。Mn = 2n − 1 が素数ならば n もまた素数である。古代ギリシア数学者は p = 57 のとき Mp が素数であることを見つけた。しかし p が素数であってもMp は素数とは限らない(例:M11 = 2047 = 23 × 89)。そのため完全数の探索は困難をきわめた。

17世紀までに p = 13, 17, 19 のとき Mp が素数であることが分かるが、1644年マラン・メルセンヌは「素数 p2p − 1 が素数になるのは、19 < p ≤ 257 では p = 31, 67, 127, 257 の4つの場合だけである」という大胆不敵な予想を公表した。しかしメルセンヌ自身はその予想を証明することができず、しかもその予想の一部は誤っていた。

成果を見るのはメルセンヌが予想を公表してから128年後、1772年オイラーp = 31 では素数)[2][10]。その次の成果はさらに104年後、1876年リュカ(効率的な素数判定法リュカ・テストEnglish版を考案、p = 67 では素数でない、p = 127 では素数[2][11])であった。その後リュカ・テストは改良が加えられ、メルセンヌが予想した範囲にない3個が付け加えられた(p = 611883年)、p = 891911年)、p = 1071914年))。メルセンヌが予想した最後の数 p = 257 について決着がついたのは1922年のことであった。残念ながらこれも合成数だった[2][12]

結局メルセンヌの4つの予想のうち2つが当たり、2つは外れた。なおかつ、間に予想できなかった3つが含まれていたことを考えれば予想は五分以上の確率とはいえないが、その後の歴史を見ても大きな原動力となり先駆的であったことに敬意を表し、素数であるメルセンヌ数をメルセンヌ素数という。

1903年10月、アメリカの数学者フランク・ネルソン・コールは実際の素因数分解を探し求め、ニューヨークで開かれたアメリカ数学会の会議で 193707721 × 761838257287 を黒板に計算し、M67 と一致することを証明した。この間一言もしゃべらず、席に戻った後、少し間を置いて拍手が沸き起こったと伝えられている[13]

1952年ラファエル・M・ロビンソンSWAC を利用して M521 から M2281 まで、5つのメルセンヌ素数を発見[2]して以降、発見にはコンピュータが使用されており、コンピュータの進歩と共に新たなメルセンヌ素数が発見されつつある。

1996年、メルセンヌ素数を発見することを目的として作られた分散コンピューティングによるプロジェクト GIMPS が発足し、35番目のメルセンヌ素数 M1,398,269(1996年11月13日、Joel Armengaud[14])以来、GIMPSによるメルセンヌ素数の発見が相次いでいる。

2008年8月23日、GIMPS は46番目の素数候補が、カリフォルニア大学ロサンゼルス校の数学部のコンピュータによって発見されたと報じた。この素数は電子フロンティア財団が賞金を懸けた1000万桁以上の最初の素数となるため、GIMPS によって同校数学部に50,000ドル、慈善事業に25,000ドル、残りを前の6つのメルセンヌ素数の発見者へ分配することになった。

2008年9月6日、GIMPS は45番目の素数候補が、ドイツで発見されたと報じた。これは、GIMPS によって発見された中では、発見順序と桁数が逆転した初めてのケースである。

素数判定法

知られている中で最大の素数が1876年以降ほぼ一貫してメルセンヌ素数である理由は、この判定法にあると言える。

リュカ・テスト

p(4j + 3) 型の素数のとき、S0 = 3, Sn = Sn−12 − 2 (n ≥ 1){Sn} を定義すると、

  • [math]M_p \not \mid S_k \ (0\leqq k\leqq p-2)[/math] ならば、Mp は合成数である
  • [math]M_p \mid S_{p-2}[/math] ならば、Mp は素数である[15][16][17]
アルゴリズム

アルゴリズムは以下の擬似コードで表される。

入力: p: (4j + 3) 型の素数であるテスト対象の整数
出力: PRIME:素数の場合, COMPOSIT:合成数の場合
Lucas_Test(p):
    var s = 3
    var MP = (1 << p) − 1
    for n in range(2, p):
        s = (s2 − 2) % MP
    if s == 0 then:
        return PRIME
    else:
        return COMPOSIT

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

p が奇素数のとき、S0 = 4, Sn = Sn−12 − 2 (n ≥ 1){Sn} を定義すると、

  • [math]M_p \not \mid S_k \ (0\leqq k\leqq p-2)[/math] ならば、Mp は合成数である
  • [math]M_p \mid S_{p-2}[/math] ならば、Mp は素数である[18][19][20]

リュカ–レーマー・テストは二進計算機用のアルゴリズムに向いており、コンピュータによるメルセンヌ素数の発見には、この判定法が用いられてきた。例えば、2p ≡ 1 (mod Mp) より、A·2p + BA + B (mod Mp) が成り立つので、Mp で割る割り算の代わりに、二進法で p 桁のシフト演算と足し算だけで計算できる。

アルゴリズム

アルゴリズムは以下の擬似コードで表される。

入力: p:奇素数であるテスト対象の整数
出力: PRIME:素数の場合, COMPOSIT:合成数の場合
Lucas_Lehmer_Test(p):
    var s = 4
    var MP = (1 << p) − 1
    for n in range(2, p):
        s = (s2 − 2) % MP
    if s == 0 then:
        return PRIME
    else:
        return COMPOSIT
入力: p:奇素数であるテスト対象の整数
出力: PRIME:素数の場合, COMPOSIT:合成数の場合
Lucas_Lehmer_Test_FAST(p):
    var s = 4
    var M = 2p − 1
    for n in range(2, p):
        var sqrt = s × s
        s = (sqrt & m) + (sqrt >> p)
        if s >= m then
            s = s − m
        s = s − 2
    if s == 0 then
        return PRIME
    else
        return COMPOSIT

メルセンヌ素数の一覧

2018年1月現在、メルセンヌ素数は50個まで知られている。ただし、メルセンヌ素数としての番号が確定しているものは47番目までであり、

p = 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, 42643801, 43112609オンライン整数列大辞典の数列 A000043, オンライン整数列大辞典の数列 A000668

における Mp がそうである。さらに48, 49, 50番目の候補として p = 57885161, 74207281, 77232917 が挙がっており、間に素数がないかどうか検証中である。

# p Mp Mp
桁数
発見日 発見者
1 2 3 1 紀元前5世紀[21] 古代ギリシアの数学者
2 3 7 1 紀元前5世紀[21] 古代ギリシアの数学者
3 5 31 2 紀元前3世紀[21] 古代ギリシアの数学者
4 7 127 3 紀元前3世紀[21] 古代ギリシアの数学者
5 13 8191 4 1456年 不明[22]
6 17 131071 6 1588年 ピエトロ・カタルディEnglish版
7 19 524287 6 1588年 ピエトロ・カタルディ
8 31 2147483647 10 1772年 レオンハルト・オイラー
9 61 2305843009213693951 19 1883年 イヴァン・パヴシンEnglish版
10 89 618970019642690137449562111 27 1911年 R・E・パワーズEnglish版
11 107 162259276829213363391578010288127 33 1914年 R・E・パワーズ[23]
12 127 170141183460469231731687303715884105727 39 1876年 エドゥアール・リュカ
13 521 68647976601306097149819007…115057151 157 1952年1月30日 ラファエル・M・ロビンソンEnglish版, 使用:SWAC
14 607 531137992…031728127 183 1952年1月30日 ラファエル・M・ロビンソン
15 1,279 104079321…168729087 386 1952年6月25日 ラファエル・M・ロビンソン
16 2,203 147597991…697771007 664 1952年10月7日 ラファエル・M・ロビンソン
17 2,281 446087557…132836351 687 1952年10月9日 ラファエル・M・ロビンソン
18 3,217 259117086…909315071 969 1957年9月8日 ハンス・リーゼル, 使用:BESK
19 4,253 190797007…350484991 1,281 1961年11月3日 アレクサンダー・フルウィッツ, 使用:IBM 7090
20 4,423 285542542…608580607 1,332 1961年11月3日 アレクサンダー・フルウィッツ
21 9,689 478220278…225754111 2,917 1963年5月11日 ドナルド・ギリース, 使用:ILLIAC II
22 9,941 346088282…789463551 2,993 1963年5月16日 ドナルド・ギリース
23 11,213 281411201…696392191 3,376 1963年6月2日 ドナルド・ギリース
24 19,937 431542479…968041471 6,002 1971年3月4日 ブライアント・タッカーマンEnglish版, 使用:IBM 360/91
25 21,701 448679166…511882751 6,533 1978年10月30日 ランドン・カート・ノルEnglish版 & ローラ・ニッケル, 使用:CDC Cyber 174
26 23,209 402874115…779264511 6,987 1979年2月9日 ランドン・カート・ノル
27 44,497 854509824…011228671 13,395 1979年4月8日 ハリー・ネルソン & デイヴィッド・スローウィンスキーEnglish版
28 86,243 536927995…433438207 25,962 1982年9月25日 デイヴィッド・スローウィンスキー
29 110,503 521928313…465515007 33,265 1988年1月28日 ウォルター・コルキット & ルーク・ウェルシュ
30 132,049 512740276…730061311 39,751 1983年9月19日[21] デイヴィッド・スローウィンスキー
31 216,091 746093103…815528447 65,050 1985年9月1日[21] デイヴィッド・スローウィンスキー
32 756,839 174135906…544677887 227,832 1992年2月19日 デイヴィッド・スローウィンスキー & ポール・ゲイジEnglish版 使用:Harwell Lab Cray-2[24]
33 859,433 129498125…500142591 258,716 1994年1月4日[25] デイヴィッド・スローウィンスキー & ポール・ゲイジ
34 1,257,787 412245773…089366527 378,632 1996年9月3日 デイヴィッド・スローウィンスキー & ポール・ゲイジ[26]
35 1,398,269 814717564…451315711 420,921 1996年11月13日 GIMPS / Joel Armengaud[14]
36 2,976,221 623340076…729201151 895,932 1997年8月24日 GIMPS / Gordon Spence[27]
37 3,021,377 127411683…024694271 909,526 1998年1月27日 GIMPS / Roland Clarkson[28]
38 6,972,593 437075744…924193791 2,098,960 1999年6月1日 GIMPS / Nayan Hajratwala[29]
39 13,466,917 924947738…256259071 4,053,946 2001年11月14日 GIMPS / Michael Cameron[30]
40 20,996,011 125976895…855682047 6,320,430 2003年11月17日 GIMPS / Michael Shafer[31]
41 24,036,583 299410429…733969407 7,235,733 2004年5月15日 GIMPS / Josh Findley[32]
42 25,964,951 122164630…577077247 7,816,230 2005年2月18日 GIMPS / Martin Nowak[33]
43 30,402,457 315416475…652943871 9,152,052 2005年12月15日 GIMPS / カーティス・クーパーEnglish版 & Steven Boone[34]
44 32,582,657 124575026…053967871 9,808,358 2006年9月4日 GIMPS / カーティス・クーパー & Steven Boone[35]
45 37,156,667 202254406…308220927 11,185,272 2008年9月6日 GIMPS / Hans-Michael Elvenich[36]
46 42,643,801 169873516…562314751 12,837,064 2009年4月12日 GIMPS / Odd Magnar Strindmo
47 43,112,609 316470269…697152511 12,978,189 2008年8月23日 GIMPS / エドソン・スミス[36]
48[*] 57,885,161 581887266…724285951 17,425,170 2013年1月25日 GIMPS / カーティス・クーパー[37][38]
49[*] 74,207,281 300376418084…391086436351 22,338,618 2015年9月17日 GIMPS / カーティス・クーパー[39]
50[*] 77,232,917 467333183359…069762179071 23,249,425 2017年12月26日 GIMPS / Jonathan Pace[40]

  •  48から50番目は、2018年4月時点でより小さなメルセンヌ素数の個数を検証できていないことによる暫定的な順位である。過去には29番目のメルセンヌ素数は30, 31番目が発見された後に発見されている。また47番目の後に45, 46番目が発見されている。

未解決問題

  • メルセンヌ素数は無数に存在するか?
  • 素数 p に対して Mp が合成数であるとき、これをメルセンヌ合成数と呼ぶことにして、それは無数に存在するか?
  • 平方因子を持つメルセンヌ数 Mpp は素数)が存在するか?
  • n を奇数とするとき、次の3つの条件のうち2つが満足されれば、残りの1つも満足されると予想されており、n < 105 に対してこの予想は正しいと確認されている[41]
  1. Mn が素数
  2. n = 2k ± 1 または 4k ± 3
  3. (2n + 1)/3 が素数

脚注

注釈

  1. 岩波数学辞典』第3版 180E ではそのようになっている。一松 (2007, p. 73) によれば、これは日本のごく一部での用法であるらしい。『岩波数学辞典』第4版 194D では、メルセンヌ数とメルセンヌ素数を使い分けている。

出典

  1. Eric W. Weisstein
  2. 2.0 2.1 2.2 2.3 2.4 2.5 淡中 1982, pp. 65–67.
  3. 中村 2008, p. 81.
  4. 4.0 4.1 和田 1981, pp. 59-61
  5. 5.0 5.1 ユークリッド 1971, 第9巻、命題36.
  6. 和田 1981, p. 192.
  7. 7.0 7.1 和田 1981, p. 193
  8. Erdős, P.; Shorey, T. N. (1976). “On the greatest prime factor of 2p − 1 for a prime p, and other expressions” (PDF). Acta Arithmetica (Institute of Mathematics Polish Academy of Sciences) 30 (3): 257-265. http://www.renyi.hu/~p_erdos/1976-28.pdf. 
  9. The Prime Pages, The Top Ten Record Primes
  10. 和田 1981, p. 51.
  11. 中村 2008, pp. 83f.
  12. 中村 2008, p. 80.
  13. 中村 2008, p. 87.
  14. 14.0 14.1 GIMPS Discovers 35th Mersenne Prime.
  15. 中村 2008, pp. 82–84.
  16. Lucas 1878.
  17. Lucas 1969.
  18. 中村 2008, pp. 84f.
  19. 和田 1981, pp. 50–52, 194–199.
  20. 和田 1999, §5 リュカ・テスト.
  21. 21.0 21.1 21.2 21.3 21.4 21.5 Landon Curt Noll, Mersenne Prime Digits and Names.
  22. The Prime Pages, Mersenne Primes: History, Theorems and Lists.
  23. The Prime Pages, M107: Fauquembergue or Powers?.
  24. The Prime Pages, The finding of the 32nd Mersenne.
  25. Chris Caldwell, The Largest Known Primes.
  26. The Prime Pages, A Prime of Record Size! 21257787 − 1.
  27. GIMPS Discovers 36th Known Mersenne Prime.
  28. GIMPS Discovers 37th Known Mersenne Prime.
  29. GIMPS Finds First Million-Digit Prime, Stakes Claim to $50,000 EFF Award.
  30. GIMPS, Researchers Discover Largest Multi-Million-Digit Prime Using Entropia Distributed Computing Grid.
  31. GIMPS, Mersenne Project Discovers Largest Known Prime Number on World-Wide Volunteer Computer Grid.
  32. GIMPS, Mersenne.org Project Discovers New Largest Known Prime Number, 224,036,583 − 1.
  33. GIMPS, Mersenne.org Project Discovers New Largest Known Prime Number, 225,964,951 − 1.
  34. GIMPS, Mersenne.org Project Discovers New Largest Known Prime Number, 230,402,457 − 1.
  35. GIMPS, Mersenne.org Project Discovers Largest Known Prime Number, 232,582,657 − 1.
  36. 36.0 36.1 Titanic Primes Raced to Win $100,000 Research Award. Retrieved on 2008-09-16.
  37. GIMPS, GIMPS Project Discovers Largest Known Prime Number, 257,885,161 − 1
  38. CASEY JOHNSTON (2013年2月7日). “「これまでで最大の素数」を発見”. WIRED (WIRED.jp). http://wired.jp/2013/02/07/volunteer-discovers-a-new-17-million-digit-prime-number/ . 2013閲覧. 
  39. Largest Known Prime, 49th Known Mersenne Prime Found!!”. Great Internet Mersenne Prime Search. . 2016閲覧.
  40. GIMPS Project Discovers Largest Known Prime Number: 277,232,917 − 1”. Great Internet Mersenne Prime Search. . 2018閲覧.
  41. P. T. Bateman, J. L. Selfridge, S. S. Wagstaff Jr., "The new Mersenne conjecture", American Mathematical Monthly, 96 (1989), 125–128.

参考文献

関連項目

外部リンク