ミラーラビン素数判定法について
ミラーラビン素数判定法はフェルマーテストを拡張した感じです。
フェルマーテストでは が素数のとき、フェルマーの小定理より と が互いに素なとき となることを利用して、 と互いに素な整数 を取って であれば合成数と判断するのでした。
ここから更に拡張します。
のとき、 で、 が素数より または となることを利用します。
というように に素因数 が出ないように分解します。
このとき、( であれば) または となります。
さらに、 のときは( であれば) または と続きます。
つまり、 が素数ならば、 が のとき となるか、全部 になるます。
これの対偶を使って、 となるか、 のどこかで となるかのどちらかにならなければ、合成数です。
この をランダムに決めて、テストしてくいくのがミラーラビン素数判定法です。
ここで、テストする数 が小さければいくつかの を使うだけで、確実に素数判定を実行できることが保証できます。
例えば、 なら、 についてのみ調べれば良いです。
実装
C++ で実装しました。
メルセンヌツイスタでランダムに生成した 個の 以下の整数について素数判定するのに手元の環境だと 1.854s
かかりました。
ロー法について
乱択で素因数を発見するアルゴリズムです。
[2] 素因数分解の高速なアルゴリズム(ロー法) | 高校数学の美しい物語 がとても分かりやすいので、アルゴリズムの内容はそちらを見てください。
実装
これの素数判定にミラーラビンを使って、C++ で実装しました。
メルセンヌツイスタでランダムに生成した 個の 以下の整数について素数判定するのに手元の環境だと 1.670s
かかりました。
最後に
何か間違いや質問などがあればお願いします。
最後まで読んでいただきありがとうございました。