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\$
0

1 Answer 1

Reset to default
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\$
3
  • \$\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\$ Commented 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\$ Commented 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\$ Commented Mar 6, 2018 at 4:41

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.