Miller-Rabin primality test


(UCM ELP) #1

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)