import random


def miller_rabin(n, k):
    """Run the Miller-Rabin test on n with at most k iterations

    Arguments:
        n (int): number whose primality is to be tested
        k (int): maximum number of iterations to run

    Returns:
        bool: If n is prime, then True is returned. Otherwise, False is
        returned, except with probability less than 4**-k.

    See <https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test>
    """
    assert n > 3

    # find r and d such that n-1 = 2^r × d
    d = n-1
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1
    assert n-1 == d * 2**r
    assert d % 2 == 1

    for _ in range(k):  # each iteration divides risk of false prime by 4
        a = random.randint(2, n-2)  # choose a random witness

        x = pow(a, d, n)
        if x == 1 or x == n-1:
            continue  # go to next witness

        for _ in range(1, r):
            x = x*x % n
            if x == n-1:
                break   # go to next witness
        else:
            return False
    return True