Optimizing Miller-Rabin Primality Test in Python

Question

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)

Answer 1

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.

• D. Senack: 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?
• Oscar Smith: I think so, but that means your code is pretty badly broken and thus more appropriate for stackoverflow or similar.
• D. Senack: 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.