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 &lt; 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.