ミラー・ラビン素数判定法とは？大きな数の素数性を高速にテストするアルゴリズムの仕組みと計算例

ミラー・ラビン素数判定法（Miller–Rabin）とは

ミラー・ラビン法は、非常に大きな数の素数性を高速に判定するための確率的アルゴリズムです。「ラビン・ミラー素数判定法」とも呼ばれ、フェルマー素数判定法やソロベイ＝シュトラッセン素数判定法と同様に、与えられた数が素数かどうかを判定します。

このテストは「素数に対して必ず成り立つ等式（または等式の集合）」に基づいています。判定対象の数に対してこれらの等式が実際に成り立つかどうかを検証することで、素数性を評価します。

ミラー・ラビン法は、現在知られている中で最も実用的な素数判定アルゴリズムの一つであり、RSA暗号などを扱う多くのソフトウェアライブラリで採用されています。代表例としては OpenSSL が挙げられます。

「素数判定」というより「合成数判定」

厳密に言えば、ミラー・ラビン法が確定的に示せるのは「その数が合成数であること」です。そのため、素数判定法というよりも合成数判定法と呼ばれることがあります。このテストはすべての合成数を見抜くことが可能で、任意の合成数 n に対して、少なくとも全体の 3/4 の数 a が n の合成性の証人（witness）として働きます。

また、ミラー・ラビン法はフェルマーの小定理を単純に拡張したものであり、フェルマーの小定理単体よりもはるかに高い確度で素数判定を行える点が大きな特徴です。

アルゴリズム：ミラー・ラビンテストの擬似コード

Miller-Rabin-Test (n, a)  // n は判定する数、a は底
{
    n − 1 = m × 2k となる m と k を求める
    T ← am mod n
    if (T = ±1) return "素数"
    for (i ← 1 to k − 1)  // k − 1 は最大ステップ数
    {
        T ← T2 mod n
        if (T = +1) return "合成数"
        if (T = −1) return "素数"
    }
    return "合成数"
}

数がミラー・ラビンテストに 1 回合格するごとに、その数が実は素数ではない確率は 1/4 以下であることが証明されています。さらに、異なる基数を用いて m 回のテストに合格すれば、素数でない確率は (1/4)^m まで低下します。

計算例：底 2 で 341 を判定する

問題： ミラー・ラビン法を底 2 で適用し、341 が合成数かどうかを判定します。

解答：

1. ステップ1： 341 − 1 = 340 = 2² × 85 より、n = 341、k = 2、m = 85。
2. ステップ2： 底 a = 2 を選択。
3. ステップ3： T = a^m mod n = 2⁸⁵ mod 341 を計算します。2¹⁰ = 1024 ≡ 1 (mod 341) なので、2⁸⁵ = (2¹⁰)⁸ × 2⁵ ≡ 1 × 32 = 32。
4. ステップ4： T = 32 ≠ ±1 なので、次のステップへ進みます。
5. ステップ5： i = 1 のとき、T = 32² mod 341 = 1024 mod 341 = 1。ここで T = 1 ≠ −1 であるため、「合成数」を返します。

したがって、341 は合成数です（実際、341 = 11 × 31）。なお、341 は底 2 に対するフェルマー擬素数として有名な数ですが、ミラー・ラビン法はこれを正しく見抜ける好例といえます。

ミラー・ラビン法のメリット

• 非常に大きな数の素数判定にも適用できます。
• 他の素数判定法と比べて処理速度に優れているため、多くの暗号技術アプリケーションで第一選択となります。
• オイラー法やソロベイ＝シュトラッセン法と比較して、誤判定（失敗）の確率が低くなっています。
• フェルマー法では、カーマイケル数 n に対してテストを欺く「嘘つき」の底が多すぎて誤り率がほぼ 1 に近づくという欠点がありますが、ミラー・ラビン法ではこの問題が効果的に回避されています。