メルセンヌ数

古代～中世

メルセンヌ素数の探求は紀元前3世紀ごろに端を発する。古代エジプトの数学者エウクレイデスは『原論』の中で、「2ⁿ − 1 が素数ならば、2^{n − 1}(2ⁿ − 1) は完全数である」ことを証明した^[8]。ここから、メルセンヌ素数の探索は完全数の探索にも繋がることとなる^{[9][注釈 1]}。

小さいメルセンヌ素数がいつから知られているかは定かではないが、少なくとも最初の4つの完全数はゲラサのニコマコスの『算術入門』ですでに言及されている^[10][11]。5番目から7番目の完全数は、13世紀イスラムの数学者イブン・ファッルース (fr:Ibn Fallus) が論文に記している^[12]。ヨーロッパでは、5番目の完全数が1456年と1461年の日付が付された古い写本に記されて^[13][14]おり、6番目と7番目のメルセンヌ素数および完全数も1603年にピエトロ・カタルディ（英: Pietro Cataldi）によって発見されている^[12]。

メルセンヌの予想

1644年、マラン・メルセンヌは「素数 p で 2^p − 1 が素数になるのは、p ≦ 257 では p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 の11個の場合だけである」という予想を公表した^[12][16]。しかしメルセンヌ自身はその予想を証明することができず、しかもその予想の一部は誤っていた。

成果をもたらしたのはメルセンヌが予想を公表してから128年後、1772年のオイラー（p = 31 では素数）^[1][17]である。その次の成果はさらに104年後、1876年、リュカ（効率的な素数判定法リュカ・テスト（英語版）を考案、p = 67 では素数でない、p = 127 では素数^[1][18]）によってもたらされた。その後リュカ・テストは改良が加えられ、メルセンヌが予想した範囲にない3個が付け加えられた（p = 61（1883年）、p = 89（1911年）、p = 107（1914年））。メルセンヌが予想した最後の数 p = 257 について決着がついたのは1922年のことであり、 p = 257 も合成数だった^[1][19]。

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

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

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

GIMPSによる発見

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

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

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

リュカ・テスト

p が (4j + 3) 型の素数のとき、S₀ = 3, S_n = S_n−1² − 2 (n ≥ 1) で {S_n} を定義すると、

• ${\displaystyle M_{p}\not \mid S_{k}\ (0\leqq k\leqq p-2)}$ ならば、M_p は合成数である
• ${\displaystyle M_{p}\mid S_{p-2}}$ ならば、M_p は素数である^[21][22][23]

入力: 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 が奇素数のとき、S₀ = 4, S_n = S_n−1² − 2 (n ≥ 1) で{S_n} を定義すると、

• ${\displaystyle M_{p}\not \mid S_{k}\ (0\leqq k\leqq p-2)}$ ならば、M_p は合成数である
• ${\displaystyle M_{p}\mid S_{p-2}}$ ならば、M_p は素数である^[24][25][26]

リュカ–レーマー・テストは二進計算機用のアルゴリズムに向いており、コンピュータによるメルセンヌ素数の発見には、この判定法が用いられてきた。例えば、2^p ≡ 1 (mod M_p) より、A·2^p + B ≡ A + B (mod M_p) が成り立つので、M_p で割る割り算の代わりに、二進法で 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 s2 = s × s
        s = (s2 & m) + (s2 >> p)
        if s >= m then
            s = s − m
        s = s − 2
    if s == 0 then
        return PRIME
    else
        return COMPOSIT