4
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\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 '18 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\$ – Oscar Smith Mar 6 '18 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 '18 at 4:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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