Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
9
Help us understand the problem. What are the problem?

More than 3 years have passed since last update.

posted at

updated at

Organization

巨大素数を見つけるアルゴリズムについて(リュカ=レーマー・テスト)

概要

史上最大の素数が更新されたというニュースが最近話題になっていました。

見つかった素数は 274207281 - 1 です。

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

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

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

判定法

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

p を 3以上の素数,
Mp を p 番目のメルセンヌ数(つまり 2p-1),
S0 = 4,
k=1, 2, 3,... に対して Sk = Sk-12 - 2.
とするとき、

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

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

実装の考え方

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

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

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

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

そして、それを 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 番目までのメルセンヌ素数が見つかりました。
メルセンヌ.png

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

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

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
9
Help us understand the problem. What are the problem?