ミラーラビンの素数判定法について
概要
- フェルマーの小定理を前提として、確率的に素数かどうかを判定するアルゴリズム
- カーマイケル数という判定をほとんどパスしてしまう数も存在している
判定方法
- ある素数をpとする
- 素数の特徴としてpが法のとき、有限体\(Z_p\) が1の時、以下のことが成り立つ
- \((x+1)\)と\((x-1)\)はpで割り切れない
- また、\((x+1) = 2^s \times d\) と表現できる
- この式を満たすaが存在するはずである
- 様々なaについて\(a^d = p\)が成立しないかチェックしていくのだが、確率的に担保することになる
- 誤る確率はk回の試行に対して\(4^{-k}\)である
pythonでの実装
import math
import random
def miller_rabin_test(p):
if p == 1:
return False
if p == 2:
return True
for _ in range(100):
a = random.randint(2, p - 1)
if math.gcd(p, a) != 1:
return False
d = p - 1
if pow(a, d, p) != 1:
return False
return True
if __name__ == '__main__':
# 2 ** 89 - 1 = 618970019642690137449562111は巨大な素数
print(miller_rabin_test(2 ** 89 - 1))