is_prime.py

JAESCHKE_PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

def is_prime_miller_rabin(n):
    if n in JAESCHKE_PRIMES:
        return True
    if (n == 1) or (n & 1 == 0):
        return False

    d = n - 1
    while (d & 1 == 0):
        d = d >> 1

    for a in JAESCHKE_PRIMES:
        if a > n:
            continue
        t = d
        y = pow(a, t, n)
        while (t != n - 1) and (y != 1) and (y != n - 1):
            y = (y * y) % n
            t = t << 1
        if (y != n - 1) and (t & 1 == 0):
            return False
    return True