## 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.

**Theory**

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

**Algorithm**

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

-fR0DDY

“If p is a prime and x^2\equiv1\pmod{p} or \left(x-1\right)\left(x+1\right)\equiv0\pmod{p} then x\equiv1\pmod{p} or a\equiv-1\pmod{p}.”

what is the significance of this statement if you please explain how this statement is true in this test??

gauravalgoAugust 22, 2011 at 1:10 PM

If p is prime and x2 = 1 ( mod p ), then x = +1 or -1 ( mod p ). We could prove this as follows:

x2 = 1 ( mod p )

x2 – 1 = 0 ( mod p )

(x-1)(x+1) = 0 ( mod p )

what is the significance of this statement if you please explain how this statement is true in this test??

gauravalgoAugust 22, 2011 at 1:14 PM

The significance is in the third statement. Let n-1 = , so By Fermat’s Little Theorem . So either such that repeated squaring from will always yield 1 or for some 0 ≤ r ≤ s-1 such that repeated squaring from it will always yield 1.

fR0DDYAugust 22, 2011 at 2:49 PM

well great !!! thanks for reply but now i want to ask why

a^d = 1 ( mod n ) why not a^d = -1 ( mod p ) as first case;

although second case brings both but my question is only for case first

please reply asap

gauravalgoAugust 25, 2011 at 6:18 PM

a^d = -1 (mod p) is considered when r=0 in the second condition for some 0 ≤ r ≤ s-1.

fR0DDYAugust 26, 2011 at 9:32 PM

Hi,

I’ve been looking all over for an answer, but I couldn’t find any. Can you please tell me why it tests if x equals 1 or x equals n-1 and what “next iteration” means?

I’m talking about these lines:

if x =1 or x = n-1

Next iteration

and

if x = N-1

Next iteration

I’m waiting for your reply, thanks a lot

carmenNovember 20, 2011 at 12:50 AM

we check x = 1 for and x = N – 1 for

Next iteration means we try for the next random value ‘a’.

fR0DDYNovember 22, 2011 at 11:57 AM

Thank you sir, such a nice explaination 🙂

Anurag AtriNovember 22, 2011 at 9:35 AM

I’m sorry I haven’t been more precise. There are two equations: a^d = 1(mod n) and a(2^r*d) = -1(mod n).

Now, for the second one, we test x = N-1. My question is why do we test both (x = 1 and x = N-1) for the first equation?

Does the answer have anything to do with the fact that x^2 = 1(mod n) ends up having two solutions? (1 and -1).

If it does, how is it possible when d is odd, and, obviously, not 2?!

Does this make sense to you? or is it just nonsense? :-s

carmenNovember 23, 2011 at 12:39 AM

Yes. See point 3 in the post.

It says a^d = a(mod n) or a^(2^r*d) = -1(mod n) for 0 <= r <= (s-1). So for r = 0, we have a^d = -1(mod n).

For example, if a is 4 and N is 5. N – 1 = 4, d = 1. So a^d = 4^1 which is equal to -1(mod 5).

fR0DDYNovember 23, 2011 at 10:56 AM

All right then.

Everything is so clear now.

Thank you for being so patient, fRODDY, and thank you for the explanation.

Have a nice day!

carmenNovember 24, 2011 at 1:29 AM

Thank you fR0DDY, this is the first implementation of MillerRabbin which works for me.

Have a nice day!

crypticMarch 30, 2012 at 3:52 PM

This works….but I implemented a similar cpp version but it is so slow. I don’t understand miller rabin is supposed to be much faster. It runs slowly for prime numbers greater than 10^9

the cake is a lieApril 2, 2012 at 11:46 PM

hi >>>>>>>i need this algorathim in matlab code ///and thanks

وردة الياسمينDecember 20, 2012 at 10:25 PM

Hi,

I’ve been wondering why the the if statement on line 9 of your pseudo code i.e. if x==1 is required and why you return false if the test succeeds?

Thank You

AkashJune 27, 2013 at 3:19 PM

THERE IS DECLARTION ERROR IS SHOWING IN ERROR

SHUBHRANSHUNovember 2, 2015 at 10:47 AM