Python implementation of the Miller-Rabin Primality Test

miller_rabin.py

def miller_rabin(n, k):

    # Implementation uses the Miller-Rabin Primality Test
    # The optimal number of rounds for this test is 40
    # See http://stackoverflow.com/questions/6325576/how-many-iterations-of-rabin-miller-should-i-use-for-cryptographic-safe-primes
    # for justification

    # If number is even, it's a composite number

    if n == 2:
        return True

    if n % 2 == 0:
        return False

    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for _ in xrange(k):
        a = random.randrange(2, n - 1)
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in xrange(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

nice work man

n = 3 causes an error at line 21.
I changed line 10 to
if n == 2 or n == 3:

which appears to solve the problem.

Thanks for this code.

Mark

Thank you.

Still getting error when running on spyder 3.7
Error:
return True
^
SyntaxError: 'return' outside function

Nice work man

Still getting error when running on spyder 3.7
Error:
return True
^
SyntaxError: 'return' outside function

You probably have left out the def function part.

Still getting error when running on spyder 3.7
Error:
return True
^
SyntaxError: 'return' outside function

You probably have left out the def function part.

probably more that there's a tab missing in the copied version. I would think that the return False on the line before it would've given the syntax error first.

Maybe its pretty basic, but at least I didn't know. If you get the error 'xrange' is not defined. Just change it for 'range'. What happens is that 'xrange' is from Python 2, which was renamed to 'range' in Python 3. You can refer here for further information:
https://stackoverflow.com/questions/17192158/nameerror-global-name-xrange-is-not-defined-in-python-3

Maybe its pretty basic, but at least I didn't know. If you get the error 'xrange' is not defined. Just change it for 'range'. What happens is that 'xrange' is from Python 2, which was renamed to 'range' in Python 3. You can refer here for further information: https://stackoverflow.com/questions/17192158/nameerror-global-name-xrange-is-not-defined-in-python-3

Also, need to import random.

For big integers it never returns (waited like 1hr), even with K=5 (int of 200k+ decimal digits). Is there any fast primality tests for such big numbers?

Maybe its pretty basic, but at least I didn't know. If you get the error 'xrange' is not defined. Just change it for 'range'. What happens is that 'xrange' is from Python 2, which was renamed to 'range' in Python 3. You can refer here for further information: https://stackoverflow.com/questions/17192158/nameerror-global-name-xrange-is-not-defined-in-python-3

Also, need to import random.

For big integers it never returns (waited like 1hr), even with K=5 (int of 200k+ decimal digits). Is there any fast primality tests for such big numbers?

This is a limit of python's arithmetic, i.e there is no known function that is both as fast or strong as the strong Fermat test. You would need to use a dedicated multi-precision library like GMP or GWNUM. Keep in mind that even with dedicated arithmetic functions integers around a million digits will take hours.