ミラーラビン素数判定法&Pythonでの実装

ミラーラビン素数判定法

整数$p>2$が素数であるとします。そして、$p-1 = 2^st$($t$は奇数)と置きます。この時$\gcd(a, p) = 1$を満たす自然数$a$について以下の２つの条件のうちどちらかが成立します。

1. $a^t \equiv 1 \mod p$
2. $a^{2^rt} \equiv -1 \mod p (0 \leqq r \leqq s-1)$

この定理が示すのは、「$p$が素数」→「条件1か2を満たす」ということです。つまり、対偶をとると、「条件1,2のどちらも満たさない」→「$p$は素数でない」となります。

ランダムに$a$を選び、判定する回数を$k$回としたとき、合成数が素数と判定されてしまう確率は$\frac{1}{4^k}$ということが知られています。

証明

前提知識：フェルマーの小定理

$p$は素数であるのでフェルマーの小定理より以下が成立します。

ところで、$p-1 = 2^st$より、

$a^{2^st} \equiv 1 \mod p$

となります。

数列$a^{2^rt}(0 \leqq r \leqq s-1)$の中に、1と合同でないものがある場合、その最大の数を$x$とします。数列で$x$の次の数、つまり$x^2$は1と合同であるので、それをもとにして以下のことが分かります。

$x$は1と合同でなかったので、$x = -1$となります。この時、$x$は条件2を満たすことになります。また、このような$x$が存在しない場合、つまり、どの$x$も１と合同の場合、条件１を満たすことになります。

Pythonでの実装

Pythonで実装したコードです。

import random

# 素数の場合はTrue、合成数の場合はFalseを返す
def miller_rabin(n):
    # 1,2,偶数はあらかじめ処理しておく
    if n == 2:
        return True
    if n == 1 or n%2 == 0:
        return False

    # n-1 = 2^s * tを満たすs, tを求める
    s = 0
    t = 1
    while (n-1 >> s)%2 == 0:
        s += 1

    t = (n-1) // pow(2, s)

    # ランダムにaを選び、条件を満たすか判定する
    # 回数を増やすことで精度が上がる
    for _ in range(10):
        a = random.randint(2, n-1)
        # 条件1の判定
        if pow(a, t, n) == 1:
            continue

        # 条件2の判定
        ok = False
        for i in range(0, s):
            if pow(a, 2**i * t, n) == n-1:
                ok = True

        if not ok:
            # 条件1,2どちらも満たさない場合は合成数
            return False

    return True

参考文献

IPUSIRON　(2017)　暗号技術のすべて　翔永社