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

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.