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

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

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

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

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

リュカ・レーマーテスト

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

・Mp｜ S_p-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で割る方法ではうまく行きそうにありません。

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

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

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

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

最初から M_p で割った余りの世界（合同式の世界）で考えます。

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

そして、それを 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)についても見ていきましょう。

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

次はM_31(=2147483647)です。

あれれ〜おかしいぞ〜。

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

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

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

つづけ

• WordPress
• Facebook
• Twitter