ミラー-ラビン素数判定法は、与えられた数が素数であるかを確率的に判定するアルゴリズムです。確定的な素数判定法ではありませんが、高速であり、実用上十分な精度で素数判定を行うことができます。特に大きな数の素数判定に有効です。
前提知識：フェルマーの小定理
ミラー-ラビン素数判定法の理解には、フェルマーの小定理が基礎となります。
フェルマーの小定理 p が素数であり、a が p と互いに素な整数であるとき、以下の式が成り立ちます。
a(p - 1) ≡ 1 (mod p)
つまり、a の (p - 1) 乗を p で割った余りは 1 になります。
ミラー-ラビン素数判定法の仕組み
ミラー-ラビン素数判定法は、フェルマーの小定理の対偶（「A ならば B」の対偶は「B でないならば A でない」）と、素数の平方根に関する性質を利用します。
判定対象の数: 奇数 n が素数であるかを判定します。
n - 1 の変形: n - 1 を 2s * d の形に変形します（d は奇数）。
- 例：n = 31 の場合、n - 1 = 30 = 21 * 15 なので、s = 1, d = 15 となります。
基数 a の選択: 2 以上 n - 2 以下の範囲から、ランダムに整数 a を選びます（これを「基数」と呼びます）。
- 例：n = 31 の場合、a として 7 を選んだとします。
判定ステップ: 以下の2つの条件のどちらかが成り立つ場合、n は合成数（素数ではない）と判定します。
- 条件1: ad mod n ≠ 1
- 例：n = 31, a = 7, d = 15 の場合、715 mod 31 = 7 となり、1 ではないので、この条件は成立しません。
- 条件2: 0 ≤ r < s を満たすすべての r に対して、a(2r * d) mod n ≠ -1
- 例：n = 31, a = 7, s = 1, d = 15 の場合、
* *r* = 0 のとき: 7<sup>(2<sup>0</sup> \* 15)</sup> mod 31 = 7<sup>15</sup> mod 31 = 7 ≠ -1 (30) * この例では *s* = 1 なので、*r* は 0 のみです。 * 結果として、7<sup>15</sup> mod 31は-1(31-1=30)に等しくないので、この条件は成立しません。
- 条件1: ad mod n ≠ 1
確率的判定: 上記の条件がどちらも成り立たない場合、n は「確率的素数」（probabilistic prime）であると判定します。これは n が高い確率で素数である可能性を示唆しますが、100% 確実ではありません。
試行回数: 異なる基数 a を選んで上記のテストを k 回繰り返します。k を大きくするほど、合成数を誤って素数と判定してしまう確率（擬素数である確率）を下げることができます。通常、k は数十回程度で十分な精度が得られます。
なぜこれで素数判定ができるのか
- フェルマーの小定理の利用: もし n が素数であれば、フェルマーの小定理から、a(n - 1) ≡ 1 (mod n) が成り立ちます。ミラー-ラビン判定法では、この条件をより厳密にした形（条件1と条件2）でチェックしています。
- 平方根の性質: もし n が素数であり、x2 ≡ 1 (mod n) であるならば、x ≡ 1 (mod n) または x ≡ -1 (mod n) が成り立ちます。条件2は、この性質を繰り返し適用して、n が合成数である証拠を探しています。
具体例：n = 561 (合成数) の場合
n = 561（カーマイケル数と呼ばれる種類の合成数）を例に、ミラー-ラビン素数判定法がどのように働くかを見ていきます。
n - 1 = 560 = 24 * 35 なので、s = 4, d = 35。
基数 a として 2 を選びます。
判定ステップ:
- 条件1: 235 mod 561 = 263 ≠ 1 → 条件1が成立
この時点で、561 は合成数であると判定できます。
まとめ
ミラー-ラビン素数判定法は、フェルマーの小定理と素数の平方根の性質を組み合わせることで、効率的かつ高精度な確率的素数判定を実現しています。確定的な判定ではありませんが、試行回数を調整することで、実用上十分な信頼性を確保できます。このため、RSA暗号などの公開鍵暗号システムにおいて、大きな素数を生成する際に広く利用されています。
Pythonでミラー-ラビン素数判定法を実装する方法は、下記の記事を参考にしてください。
この他の素数判定法についてもまとめています。
