Miller Rabin Primality Test
Miller Rabin Primality Test is a probabilistic test to check whether a number is a prime or not. It relies on an equality or set of equalities that hold true for prime values, then checks whether or not they hold for a number that we want to test for primality.
1> Fermat’s little theorem states that if p is a prime and 1 ≤ a < p then
2> If p is a prime and or then or
3> If n is an odd prime then n-1 is an even number and can be written as . By Fermat’s Little Theorem either or for some 0 ≤ r ≤ s-1.
4> The Miller–Rabin primality test is based on the contrapositive of the above claim. That is, if we can find an a such that and for all 0 ≤ r ≤ s-1 then a is witness of compositeness of n and we can say n is not a prime. Otherwise, n may be a prime.
5> We test our number N for some random a and either declare that N is definitely a composite or probably a prime. The probably that a composite number is returned as prime after k itereations is
Input :A number N to be tested and a variable iteration-the number of 'a' for which algorithm will test N. Output :0 if N is definitely a composite and 1 if N is probably a prime. Write N as For each iteration Pick a random a in [1,N-1] x = mod n if x =1 or x = n-1 Next iteration for r = 1 to s-1 x = mod n if x = 1 return false if x = N-1 Next iteration return false return true
Here’s a python implementation :
import random def modulo(a,b,c): x = 1 y = a while b>0: if b%2==1: x = (x*y)%c y = (y*y)%c b = b/2 return x%c def millerRabin(N,iteration): if N<2: return False if N!=2 and N%2==0: return False d=N-1 while d%2==0: d = d/2 for i in range(iteration): a = random.randint(1, N-1) temp = d x = modulo(a,temp,N) while (temp!=N-1 and x!=1 and x!=N-1): x = (x*x)%N temp = temp*2 if (x!=N-1 and temp%2==0): return False return True