Python implementation of Miller-Rabin primality test

miller_rabin.py

def is_prime(n):
    """A very basic implementation of the Miller-Rabin primality test."""
    
    #from Wikipedia: "if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17."
    small_primes = {2,3,5,7,11,13,17}
    if n in small_primes: return True
    if n < 2 or n & 1 == 0: return False

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

    def trial(a):
        x = pow(a, d, n)
        if x == 1 or x == n-1:
            return True
        for _ in range (r):
            x = pow(x, 2, n)
            if x == n-1:
                return True
        return False

    for p in small_primes:
        if not trial(p):
            return False

    return True