概要

見つかった素数は 2^74207281 - 1 です。

この数のように、2ⁿ-1 の形で書ける数を「メルセンヌ数」と呼ぶのですが、
実は現在見つかっている巨大素数のほとんどがこのメルセンヌ数です。

これは何故かというと、メルセンヌ数だけに特別に使える優れた素数判定法が存在するからです。

その一つが「リュカ=レーマー判定法」です。
今回はそれをpython3で簡単に実装してみたいと思います。

判定法

（※実装だけ知りたい人は飛ばしてください）

p を 3以上の素数,
M_p を p 番目のメルセンヌ数（つまり 2^p-1）,
S₀ = 4,
k=1, 2, 3,... に対して S_k = S_k-1² - 2.
とするとき、

S_p-2 が M_p で割り切れるなら、
M_p は素数である。

ここで入力 p を素数に限っているのは、p が合成数なら M_p も合成数になると知られているからです（証明は因数分解を使ったもので初等的）。

（※実装そのものだけ知りたい人は飛ばしてください）

まず、上のアルゴリズムを素直に実装すると、S_p-2 が大きくなり過ぎてしまいます。

最終的に知りたいのは S_p-2 の値そのものではなく、それが M_p
で割り切れるかどうかなので、
最初から M_p で割った余りの世界（合同式の世界）で考えます。

つまり実装では、S_k = S_k-1² - 2 の計算をするたびに M_p で割った余りを取り、あつかう数を小さくしていきます。

そして、それを p-2 回繰り返して最終的に 0 になれば、余りも 0、すなわち割り切れたということになります。

def Lucas_Lehmer_Test(p):
    s = 4 #S_0の定義
    M = (1 << p) - 1 #左シフトで2^pを作る

    for n in range(2, p):
        s = (s**2 - 2) % M
    return s == 0

（入力が 3 以上の整数であることを前提としています）

試しに range(3, 3000, 2) でメルセンヌ素数を探してみたところ、
おんぼろノートPCで 50 秒ほどかかって 17 番目までのメルセンヌ素数が見つかりました。

その中で最大の 2²²⁸¹-1 は 687 桁の数なので、
普通に素数判定をしようとするとかなり難しい大きさです。
（例えば 2048bit の RSA暗号で使われるような素数で 617桁）

それだけメルセンヌ数は恵まれているということですね。

ちなみに上記のプログラムでは、単純化のため入力 p が合成数の時も実行しています。
p に対する素数判定も入れて、合成数の時はすぐにFalseを返すようにするとより早くなると思います。