rabinmiller primality test returning false implies that n is guaranteed composite returning true means that n is probably prime with a 4 k chance of being wrong factor n into a power of 2 times an odd number power 0 while num 2 0 num 2 power 1 return power num def validwitnessa x powinta intd intn if x 1 or x n 1 return false for in ranger 1 x powintx int2 intn if x 1 return true if x n 1 return false return true precondition n 5 if n 5 return n 2 or n 3 true for prime r d pow2factorn 1 for in rangek if validwitnessrandom randrange2 n 2 return false return true factor n into a power of 2 times an odd number returns true if a is a valid witness for n a valid witness increases chances of n being prime an invalid witness guarantees n is composite precondition n 5 true for prime
import random


def is_prime(n, k):

    def pow2_factor(num):
        
        power = 0
        while num % 2 == 0:
            num /= 2
            power += 1
        return power, num

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

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

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

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

        return True

    
    if n < 5:
        return n == 2 or n == 3  

    r, d = pow2_factor(n - 1)

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

    return True