# Optimizing Miller-Rabin Primality Test in Python

I'm writing a Miller-Rabin primality test in Python. While I've briefly looked at how others approached the problem, I decided to try solving the problem on my own. Aside from my choice of language, how could I go about optimizing this code? Any suggestions are welcome and don't hesitate to be brutally honest.

def miller_rabin_primality_test(n):

def mr_check_one(n):
m = n - 1
n = n - 1
k =  1

while n % 2**k == 0:
m = n / 2**k
k = k + 1

return(m)

def mr_check_two(n, m, a = [2, 3]):

for i in range(0, len(a)):
a = a[i]
b = pow(a, m, n)
i = 0

if(b == n - 1 or b == 1):
return True

while(b != n - 1 and i < 7):
b = pow(b, 2, n)
i = i + 1

if(b != n - 1):
return False
else:
return True

m =  mr_check_one(n)
r = mr_check_two(n, m)

return(r)


One obvious change to make is that mr_check_one(n) does a much more expensive loop than necessary. Here is a much simpler and faster version.

def mr_check_one(n):
m = n - 1

n = n - 1
k =  1
while n % 2 == 0:
k += 1
n /= 2

return(m / 2**k)


Also, your second function seems really broken. You allegedly loop over a, but in your first time through you redefine a, reset i and return before going through the loop more than once.

• Thanks for the suggestion on the first function. As for the second, I want to check all results of mr_check_one for 2^m mod n AND 3^m mod n (m being the result of mr_check_one). I was trying to loop over again with a different "a" value. Does that make any sense? I wasn't really sure how to go about it. Any ideas? – D. Senack Mar 6 '18 at 3:45
• I think so, but that means your code is pretty badly broken and thus more appropriate for stackoverflow or similar. – Oscar Smith Mar 6 '18 at 3:50
• I rewrote the second function. Hopefully, it's a little better. At a minimum, it is more modular and, perhaps, easier to understand. If you still think it seems pretty badly broken I'll post it over at StackOverflow. Thanks for the insights. – D. Senack Mar 6 '18 at 4:41