吟遊詩人の素数探索その2〜リュカ・レーマーテスト〜

どうも吟遊詩人です。今回も素数探索、やっていきますよ。

前回、メルセンヌ数の素数を探索していくというお話をしました。

https://ginyusizin.com/2019/11/09/0016/

今回は実際にメルセンヌ数の素数判定に用いられているリュカ・レーマーテストについてお話します。

リュカ・レーマーテスト

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

・Mp| Sp-2 ならば、Mp は素数である

出典: フリー百科事典『ウィキペディア(Wikipedia)』:メルセンヌ数

M_pがS_p-2で割り切れることはM_pが素数であることの必要十分条件であるようです。

詳しくはリュカ–レーマー・テストの証明を参照とのことですが……ちょっと難しくてまだ理解できていません。(無理数のmodQって何?)

とりあえず、実際に計算してみます。

まず、表計算ソフトで計算してみました。B列にS_p-2, C列にMp, D列にS_p-2をMpで割った値があります。

M_3(=7)やM_7(31)は割り切れているため、正しく素数と判定されています。

しかし、素数であるはずのM_7(=127)は素数であるのに、余りが出てしまっています。

これはS_p-2が2乗で急激に大きくなってしまっているため、浮動小数点型になり、正確な割り算ができなくなっているためです。

よって、実際の計算の際には、S_p-2を直接Mpで割る方法ではうまく行きそうにありません。

実装の考え方については以下の記事を参考にします。

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

最終的に知りたいのは Sp-2 の値そのものではなく、それが Mp

で割り切れるかどうかなので、

最初から Mp で割った余りの世界(合同式の世界)で考えます。

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

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

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

つまり、

ということらしい?(本当か?)

ではこのやり方でやり直してみましょう。

まず、M_7(=127)に対してリュカ・レーマーテストをしてみます。

上の表では、まずS_1=14を初項として、127で割った余りを求めています。

出てきた余りを2乗して2をひいた後、また127で割った余りを求めています。

p=7なので、p-2=5まで繰り返すと、余りが0となり、S_p-2=S_5がM_7で割り切ることができました。

次にM_19(=524287)についても見ていきましょう。

ちゃんと余りが0となっていますね。

次はM_31(=2147483647)です。

あれれ〜おかしいぞ〜。

どうやらMpが32ビット近くになると計算できなくなるようですね。

というわけで、これ以上大きい数に対してはpythonを使って検証していきたいと思います。

(今回19ビットの計算を17回繰り返したわけですが、最終的には2147483647ビットの計算を2147483645回繰り返さないといけないんですよね?本当に大丈夫?)

つづけ

吟遊詩人の素数探索その2〜リュカ・レーマーテスト〜” への1件のフィードバック

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中