The Miller-Rabin primality test is an algorithm which determines whether a given number is prime.
The test is a probabilistic method based on Fermat’s method. Mathematical concepts are very good explained in wikipedia, I suggest reading the explanation to understand the algorithm properly.
import random #Miller-Rabin primality test. Input: n=some number > 3, k=number of iterations def miller_rabin_test(n,k): r,d = miller_rabin_factoring(n-1) #factorization function while(k != 0): i=1 witnessloop = False #witnessloop is false when n is not a prime number random_num = random.randint(2,n-2) x = (random_num**d)%n if x == 1 or x == n-1: witnessloop = True while i < r: x = (random_num**((2**i)*d) % n) if(x == n-1): witnessloop = True break i = i+1 k = k-1 if witnessloop == False: return False return True def miller_rabin_factoring(n): r = 1 while((n%(2**r)) != 0) or ((n/(2**r))%2 == 0): r = r+1 d = n/(2**r) return int(r),int(d)