Miller-Rabin 素数判定法 は、正整数 $n$ が与えられたときに、「 $n$ が素数であるか否か」を判定する確率的アルゴリズムである。

1 回の試行にかかる計算量は $O(\log^3 n)$ であり、シンプルな $O(\sqrt{n} \log^2 n)$ のアルゴリズム¹と比べて非常に高速である。 $\frac{1}{4}$ 以下の確率で「 $n$ が合成数なのに素数と判定する」という誤りをするが、試行回数を $s$ 回に増やせば誤る確率を $4^{-s}$ 以下に減らせる。

この記事では、より単純だが欠点のある「Fermat テスト」を先に説明し、これを改良する形で「Miller-Rabin 素数判定法」を説明する。

Fermat テスト

Fermat テストでは、以下の Fermat の小定理 を利用する。

この対偶を取ると、以下のようになる。 $p$ が $n$ に変わっていることに注意。

命題 2 より、 $a^{n-1} \not\equiv 1 \pmod{n}$ を満たす$n$ 未満の正整数 $a$ を 1 つ見つければ、「 $n$ は素数でない」と断言できる。このように、「 $n$ は素数でない」と断言する証拠となる $a$ を 証人 (witness)という。

アルゴリズム

「証人が出るまで $a$ を乱択しよう」というのが Fermat テスト である。

1. $1 \leq a \lt n$ を満たす整数 $a$ を乱択する。
2. $(a^{n-1} \bmod{n}) \neq 1$ ならば「 $n$ は素数でない」と出力して終了する。
3. 「 $n$ は多分素数である」と出力する。

$a^{n-1} \bmod{n}$ は二分累乗法によって $O(\log n)$ の乗算・剰余算で求まるので、乗算・剰余算の計算量を $O(\log^2 n)$ とした場合、Fermat テスト 1 回の計算量は $O(\log^3 n)$ となる。

確率評価

$n$ が合成数なら証人は必ず存在する²ので、試行回数を増やすことで精度をいくらでも上げることができる。しかし $n$ によっては証人がとても少ないケースもある。

そのようなケースの例として、 $n=1729$ の場合を考える。この $1729$ は特殊な合成数で、 $1729$ と互いに素な任意の整数 $a$ について $a^{1728} \equiv 1 \pmod{1729}$ が成り立つ³。 よって $n$ と互いに素でない $a$ のみが証人となり、その割合は全体の $25 \%$ となる。 これはまだ現実的だが、同じ性質を持つ $n=410041$ では $4.5 \%$ しかなくなる。

このように、証人の割合が $n$ に大きく依存してしまうことが Fermat テストの欠点と言える。

Miller-Rabin 素数判定法

Fermat テストよりも厳しい判定方法を使うことで、証人の割合を増やしたものが Miller-Rabin 素数判定法 である。 「証人が出るまで $a$ を乱択する」という全体の流れは Fermat テストと同じである。

Miller-Rabin 素数判定法では、Fermat の小定理に加えて以下の命題を用いる。

この対偶を取ると以下のようになる。

この補題を、 $a^{n-1} \bmod{n}$ を求める過程で適用する。

アルゴリズム

まず $n=1$ または $n$ が偶数の場合、判定は自明なので除外する。以降 $n$ が $3$ 以上の奇数の場合のみを考える。

$n - 1$ は偶数なので、 $n - 1 = 2^t u$ を満たす正整数 $t$ と奇数 $u$ が一意に定まる。 この $t,u$ を用いて、以下のアルゴリズムで $n$ が素数か否かを判定する。

1. $1 \leq a \lt n$ を満たす整数 $a$ を乱択する。
2. $x_i = a^{2^i u} \bmod{n}$ なる長さ $t+1$ の数列 $(x_0, x_1, \cdots, x_t)$ を計算する。
3. もし $x_{i+1} = ({x_i}^2 \bmod{n}) = 1$ かつ $x_i \neq 1, n-1$ なる $i$ が見つかれば、「 $n$ は素数でない」と出力して終了する (命題 4)。
4. $x_t = (a^{n-1} \bmod{n}) \neq 1$ なら「 $n$ は素数でない」と出力して終了する (命題 2)。
5. 「 $n$ は多分素数である」と出力する。

$a^{n-1} \bmod{n}$ を求める過程である手順 3 で、命題 4 を用いて判定している点が変更点である。 計算量は Fermat テスト同様 $O(\log^3 n)$ となる。

確率評価

Fermat テストでは証人の割合が $n$ に大きく依存していたことが問題だった。 一方、Miller-Rabin 素数判定法では以下の定理が成り立つ。証明は難しいので割愛。

すなわち、乱択で証人を引ける確率はどんな $n$ でも $\frac{3}{4}$ 以上となる。 よって $s$ 回の試行を行った場合、このアルゴリズムが誤る、すなわち $s$ 回で一度も証人を引けない確率は $4^{-s}$ 以下となる。

実装例

Miller-Rabin 素数判定法を Python3 で実装すると以下のようになる。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

import random


# aはnの証人となる(= nは素数でないと分かる)ならTrue
def witness(n, a):
    t, u = 0, n - 1
    while u & 1 == 0:
        t += 1
        u >>= 1
    # n-1 = 2^t * u

    x = pow(a, u, n)
    # x_0 = a^u mod n

    for _ in range(t):
        y = x * x % n
        # x_{i+1} = (x_i)^2 mod n

        if y == 1:
            # (x^2 mod n) = 1

            if x != 1 and x != n - 1:
                return True
            else:
                # 以降全て1なのでOK
                return False
        x = y

    # x_t = (a^{n-1} mod n) != 1
    return True


# nが素数か判定 試行回数s
def miller_rabin(n, s):
    # 自明なケースを処理
    if n == 1:
        return False
    if n % 2 == 0:
        return n == 2

    for _ in range(s):
        a = random.randint(1, n - 1)
        if witness(n, a):
            return False
    return True