COME ON CODE ON

A blog about programming and more programming.

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 $a^{p-1}\equiv1\pmod{p}.$
2> 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 $x\equiv-1\pmod{p}.$
3> If n is an odd prime then n-1 is an even number and can be written as $2^{s}.d$. By Fermat’s Little Theorem either $a^{d}\equiv1\pmod{n}$ or $a^{2^r\cdot d}\equiv -1\pmod{n}$ 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 $a^{d}\not\equiv1\pmod{n}$ and $a^{2^r\cdot d}\not\equiv -1\pmod{n}$ 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 $4^{-k}.$

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 $2^{s}.d$
For each iteration
Pick a random a in [1,N-1]
x = $a^{d}$ mod n
if x =1 or x = n-1
Next iteration
for r = 1 to s-1
x  = $x^{2}$ 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

Written by fR0DDY

September 18, 2010 at 12:23 PM

16 Responses

1. “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??

gauravalgo

August 22, 2011 at 1:10 PM

2. 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??

gauravalgo

August 22, 2011 at 1:14 PM

• The significance is in the third statement. Let n-1 = $d.2^{s}$, so By Fermat’s Little Theorem $a^{d.2^{s}}\equiv1\pmod{n}$. So either $a^{d}\equiv1\pmod{n}$ such that repeated squaring from $a^{d}$ will always yield 1 or $a^{2^r\cdot d}\equiv -1\pmod{n}$ for some 0 ≤ r ≤  s-1 such that repeated squaring from it will always yield 1.

fR0DDY

August 22, 2011 at 2:49 PM

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

gauravalgo

August 25, 2011 at 6:18 PM

• a^d = -1 (mod p) is considered when r=0 in the second condition $a^{2^r\cdot d}\equiv -1\pmod{n}$ for some 0 ≤ r ≤  s-1.

fR0DDY

August 26, 2011 at 9:32 PM

4. 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?
if x =1 or x = n-1
Next iteration

and

if x = N-1
Next iteration

carmen

November 20, 2011 at 12:50 AM

• we check x = 1 for $x \equiv 1\pmod{N}$ and x = N – 1 for $x \equiv -1\pmod{N}$

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

fR0DDY

November 22, 2011 at 11:57 AM

5. Thank you sir, such a nice explaination 🙂

Anurag Atri

November 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

carmen

November 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).

fR0DDY

November 23, 2011 at 10:56 AM

6. 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!

carmen

November 24, 2011 at 1:29 AM

7. Thank you fR0DDY, this is the first implementation of MillerRabbin which works for me.
Have a nice day!

cryptic

March 30, 2012 at 3:52 PM

8. 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 lie

April 2, 2012 at 11:46 PM

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

وردة الياسمين

December 20, 2012 at 10:25 PM

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

Akash

June 27, 2013 at 3:19 PM

11. THERE IS DECLARTION ERROR IS SHOWING IN ERROR

SHUBHRANSHU

November 2, 2015 at 10:47 AM