from random import randint
import math
#caculate a^p(mod m)
def computeModuloPower(a, p, m):
result = 1
p_bin = bin(p)[2:]
length = len(p_bin)
for i in range(0, length):
result = result ** 2 % m
if p_bin[i] == '1':
result = result * a % m
return result
#miller_rabin one time, 2 <= b <= n-1, n is odd >= 3
def miller_rabin(b, n):
s = math.floor(math.log(n-1, 2))
t = 1
while s > 0:
t = (n - 1) // 2 ** s
if (n - 1) % 2 ** s == 0 and t % 2 == 1: #n-1 = t * 2^s
break
s = s - 1
r0 = computeModuloPower(b, t, n) #caculate r0 = b^t(mod n)
if r0 == 1 or r0 == n - 1:
return True
else:
for i in range(1, s+1):
r1 = r0 ** 2 % n
if r1 == n - 1:
return True
r0 = r1
return False
#miller_rabin k times
def test_miller_rabin(n, k):
while k > 0:
if n == 1:
return False
if n == 2:
return True
if n > 2 and n % 2 == 0:
return False #make sure n is odd >= 3
b = randint(2, n - 1)
if not miller_rabin(b, n):
return False
k = k - 1
return True
print("Please enter the integer you want to test:")
n = eval(input())
print("Please enter the test times:")
k = eval(input())
if (test_miller_rabin(n, k) == True):
print("Passed the Miller Rabin prime test, may be a prime!")
else:
print("Failed to the Miller Rabin prime test, not a prime!")
"""test examples:
test_miller_rabin(6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151, 50) = True
test_miller_rabin(1871, 20) = True
test_miller_rabin(22, 20) = False
test_miller_rabin(2, 20) = True
test_miller_rabin(58677, 30) = False
"""