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         


    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
                return True

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


1 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.

  • \$\begingroup\$ 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? \$\endgroup\$
    – D. Senack
    Mar 6, 2018 at 3:45
  • \$\begingroup\$ I think so, but that means your code is pretty badly broken and thus more appropriate for stackoverflow or similar. \$\endgroup\$ Mar 6, 2018 at 3:50
  • \$\begingroup\$ 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. \$\endgroup\$
    – D. Senack
    Mar 6, 2018 at 4:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.