Miller-Rabin (ミラーラビン) 素数判定法とは、与えられた整数が素数かどうかを判定する確率的アルゴリズムの一つです。 Python での本アルゴリズムの実装例を示します。
Miller-Rabin素数判定法のアルゴリズムは次の通りです。
-
Miller-Rabin素数判定法
$n$ を測定対象の整数とする。
- $n-1 = 2^k m$ となる $k,m$ を計算する。
- $2 \le a \le n-1$ を満たす整数 $a$ を無作為に選ぶ
- $b = a^m \mod n$ を計算する
- $b \equiv 1 \pmod{n}$ なら「$n$は素数である」と判定して停止する
- $i = 0$ から $k-1$ について、以下の計算を行う
- $b \equiv -1 \pmod{n}$ なら「$n$は素数である」と判定して停止する
- $b = b^2 \mod n$ を計算する
- 「$n$は合成数である」と判定して停止する
このアルゴリズムで、$n$が合成数のとき「$n$は素数である」と判定される確率は $1/4$ 以下
Miller-Rabin素数判定法のPythonプログラムは次の通りです。
# Miller-Rabin素数判定法
# nを測定対象の整数とする。
# このアルゴリズムで、nが合成数のとき「nは素数である」と判定される確率は 1/(4^10) 以下
def miller_rabin_test(n):
if n <= 1:
return False
# (1) n-1 = 2^k * m となる k,m を計算する
k = 0
m = n - 1
while m & 1 == 0:
k += 1
m >>= 1
assert(2**k * m == n - 1)
def trial(n):
# (2) 2 ≦ a ≦ n-1 を満たす整数 a を無作為に選ぶ
a = random.randint(2, n - 1)
# (3) b = a^m mod n を計算する
b = pow(a, m, n)
# (4) b = 1 (mod n) なら「nは素数である」と判定して停止する
if b == 1:
return True
# (5) i = 0 から k-1 について、以下の計算を行う
for i in range(0, k):
# (5.1) b = -1 (mod n) なら「nは素数である」と判定して停止する
if b == n - 1:
return True
# (5.2) b = b^2 mod n を計算する
b = pow(b, 2, n)
# (6) 「nは合成数である」と判定して停止する
return False
# 繰り返しテストすることで誤った判定の確率を下げる
for i in range(10):
if not trial(n):
return False
return True
様々な整数で素数判定をした結果は以下の通りになります。
miller_rabin_test(10) # => False
miller_rabin_test(11) # => True
miller_rabin_test(12) # => False
miller_rabin_test(13) # => True
miller_rabin_test(57) # => False
miller_rabin_test(389754788748510373) # => True
miller_rabin_test(389754788748510379) # => False
miller_rabin_test(389754788748510389) # => True
判定の正確度
1回の判定で 3/4 以上の確率で合成数をふるい落とすことができます。 上のプログラムでは繰り返しテストする回数を10としていますが、試行回数をより多くすれば、正確度は高くなります。
また、他の確率的素数判定法である Fermat 法や Solovay-Strassen 法と比較して、Miller-Rabin 法はより高い確率で判定ができる、つまり素数を選り分ける能力が高いと言われています。
なお、Lucas–Lehmer法という素数判定法では強擬素数を合成数と判定することが可能になるので、実際に ANXI X9.80 では Miller-Rabin 法を数個の基底に関して実行した後に、Lucas-Lehmer 法を1度行うことが推奨されています1。