trjhtr

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.