(n, k)
return True
returns true if a is a valid 'witness' for n
    a valid witness increases chances of n being prime
    an invalid witness guarentees n is composite
returns true if a is a valid 'witness' for n
    a valid witness increases chances of n being prime
    an invalid witness guarentees n is composite
returns true if a is a valid witness for n a valid witness increases chances of n being prime an invalid witness guarentees n is composite
def is_prime(n, k):
    r, d = pow2_factor(n - 1)

    """
    returns true if a is a valid 'witness' for n
    a valid witness increases chances of n being prime
    an invalid witness guarentees n is composite
    """

    def valid_witness(a):
        x = pow(a, d, n)

        if x == 1 or x == n - 1:
            return False

        for _ in range(r - 1):
            x = pow(x, 2, n)

            if x == 1:
                return True
            if x == n - 1:
                return False

        return True

    for _ in range(k):
        if valid_witness(random.randrange(2, n - 2)):
            return False

    return True
def is_prime ( n , k ) : r , d = pow2_factor ( n - 1 ) def valid_witness ( a ) : x = pow ( a , d , n ) if x == 1 or x == n - 1 : return False for _ in range ( r - 1 ) : x = pow ( x , 2 , n ) if x == 1 : return True if x == n - 1 : return False return True for _ in range ( k ) : if valid_witness ( random . randrange ( 2 , n - 2 ) ) : return False return True