COME ON CODE ON

A blog about programming and more programming.

Miller Rabin Primality Test

with 16 comments

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

Advertisements

Written by fR0DDY

September 18, 2010 at 12:23 PM

16 Responses

Subscribe to comments with RSS.

  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
    please reply asap

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

    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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: