ｼﾞｮｲｼﾞｮｲｼﾞｮｲ

ｼﾞｮｲｼﾞｮｲｼﾞｮｲｼﾞｮｲｼﾞｮｲ

ミラーラビン素数判定法とロー法

ミラーラビン素数判定法について

ミラーラビン素数判定法はフェルマーテストを拡張した感じです。

フェルマーテストでは $p$ が素数のとき、フェルマーの小定理より $a$ と $p$ が互いに素なとき $a^{p-1} \equiv 1 \pmod p$ となることを利用して、 $n$ と互いに素な整数 $a$ を取って $a^{n-1} \not \equiv 1 \pmod n$ であれば合成数と判断するのでした。

ここから更に拡張します。

$x^{2} \equiv 1 \pmod p$ のとき、 $(x-1)(x+1) \equiv 0 \pmod p$ で、 $p$ が素数より $x \equiv 1$ または $x \equiv -1$ となることを利用します。

$(n-1) = 2^{q} d$ というように $d$ に素因数 $2$ が出ないように分解します。

このとき、（ $q \ge 1$ であれば） $a^{2^{q-1}d} = 1$ または $a^{2^{q-1}d} = -1$ となります。

さらに、 $a^{2^{q-1}d} = 1$ のときは（ $q \ge 2$ であれば） $a^{2^{q-2}d} = 1$ または $a^{2^{q-2}d} = -1$ と続きます。

つまり、 $p$ が素数ならば、 $a^{2^{q-i}d}$ が $i = 0, 1, 2, ... q$ のとき $1, 1, ..., 1, -1, ?, ?, ...$ となるか、全部 $1$ になるます。

これの対偶を使って、 $a^{d} = 1$ となるか、 $a^{2^{q-i}d} (1 \le i \le q-1)$ のどこかで $-1$ となるかのどちらかにならなければ、合成数です。

この $a$ をランダムに決めて、テストしてくいくのがミラーラビン素数判定法です。

ここで、テストする数 $n$ が小さければいくつかの $a$ を使うだけで、確実に素数判定を実行できることが保証できます。

例えば、 $n \le 4759123140 (\ge 2^{32})$ なら、 $a = 2, 7, 61$ についてのみ調べれば良いです。

実装

C++ で実装しました。

gist.github.com

メルセンヌツイスタでランダムに生成した $10^{6}$ 個の $10^{9}$ 以下の整数について素数判定するのに手元の環境だと 1.854s かかりました。

ロー法について

乱択で素因数を発見するアルゴリズムです。

[2] 素因数分解の高速なアルゴリズム（ロー法） | 高校数学の美しい物語がとても分かりやすいので、アルゴリズムの内容はそちらを見てください。

実装

これの素数判定にミラーラビンを使って、C++ で実装しました。

gist.github.com

メルセンヌツイスタでランダムに生成した $10^{5}$ 個の $10^{9}$ 以下の整数について素数判定するのに手元の環境だと 1.670s かかりました。

最後に

何か間違いや質問などがあればお願いします。

最後まで読んでいただきありがとうございました。

参考文献

[1] ミラー–ラビン素数判定法 - Wikipedia

[2] 素因数分解の高速なアルゴリズム（ロー法） | 高校数学の美しい物語