Here is my code:
import random
def miller(n, k):
"""
takes an integer n and evaluates whether it is a prime or a composite
n > 3, odd integer to be tested for primality
k, rounds of testing (the more tests, the more accurate the result)
"""
temp = n - 1 # used to find r and d in n = 2**d * r + 1, hence temporary
r = 0
while True:
if temp / 2 == type(int):
r += 1
else:
d = temp
break
temp = temp / 2
for _ in range(k):
a = random.SystemRandom().randrange(2, n - 2)
x = a**d % n
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = x**2 % n
if x == n - 1:
continue
return "Composite"
return "Probably prime"
Certainly there must be more effective ways to implement the algorithm in Python, so that it may handle large integers with ease?
Cheers