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)
```