Rustでリュカ・レーマーテストを実装する

こちらの書籍でリュカ・レーマーテストの名前を知りました。

完全数(Perfect Number)とメルセンヌ数 (Mersenne Number) $2^{n} - 1$ の関係は有名ですが、メルセンヌ数の中で素数であるもの、即ちメルセンヌ素数(Mersenne Prime)を判定するのに使われる効果的な手法の一つがこのリュカ・レーマーテストです。

（いきなり余談ですが元となるアルゴリズムを考案したフランスの数学者エドゥアール・リュカはあのハノイの塔の開発者でもあります。）

この手法は、強力なわりにアルゴリズムがとてもシンプルです。

数列 $S _ {n}$ を $S _ {1} = 4, S _ {n+1} = S _ {n}^2 - 2$ とおく。
奇素数 $p$ について $2^{p} - 1$ で $S _ {p-1}$ が割り切れるとき、 $2^{p} - 1$ は素数である。

以上です。（証明となるとやや知識を要するので気になる方はググってください。）

アルゴリズムさえ手に入れば、あとは実装するだけです。今回は初めてRustを書いてみました。

奇素数なので一番最初の完全数 $6=1+2+3=1\times2\times3$ は含まれていませんが、この短いコードで完全数のうち小さい方から10個の数が得られたことになります。

今回計算したメルセンヌ素数のうち一番大きいのは10個目の $2^{89} - 1$ です。
ちなみに2022年4月現在で発見されている最大のメルセンヌ素数は $2^{82589933}－1$ です。

これは51番目のメルセンヌ素数で、桁数は24862048桁。テキストファイルでも25MBほどあります。

巨大な素数を発見するのに、必ずしも素因数分解が必要ではないということを知れたのは数論を勉強し始めて最初に感動したトピックです。

すっかりC#とシェーダーくらいしか書かない生活でしたので、久しぶりに新しい言語をと思い新年度からRustを勉強し始めました。今回は環境構築からだったので少し時間がかかりました。

新しい言語を学ぶのは手軽に成長感が実感できてとても良いですね。

Continue(s)