Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Miller-Rabin Algorithm
3.
Implementation
3.1.
C++
3.2.
Java
3.3.
Python
3.4.
Output
4.
Complexity
5.
Important Facts
6.
Frequently Asked Questions
6.1.
What is the RSA algorithm in cryptography?
6.2.
What is the full form of RSA and AES?
6.3.
What is the time complexity for the Miller-Rabin test?
6.4.
Where is the Miller-Rabin test used?
6.5.
What is cryptography?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Introduction to the Miller-Rabin Algorithm

Author soham Medewar
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

We often encounter a problem in identifying whether a number is prime or not. Regular algorithms might take O(n) or O(sqrt(n)) time to identify whether a number is prime or not. In this article, we will learn a Monte Carlo algorithm for composites which is called as Miller-Rabin algorithm. Miller-Rabin algorithm is also called a strong pseudo prime test. This method is a probabilistic method which is better than Fermat’s method.

miller-rabin

So, are you ready to learn? Let us start with the pseudo-code of the Miller-Rabin algorithm.

Miller-Rabin Algorithm

This algorithm returns the value true if the number is prime. It returns false if the is composite.

The Miller-Rabin algorithm takes two numbers as input, say n, k. Here n is the number on which we perform the Miller-Rabin test. The integer k determines the accuracy level. The accuracy of the Miller-Rabin algorithm increases with the increase in the value of k

Pseudo Code

bool Miller-Rabin(int k, int n)

1. Handling base case for n < 3

2. If the value of n is even, return false.

3. Determine an odd number 'd' such that n-1 can be expressed as d*2r. Because n is odd, (n-1) must be even, and r must be bigger than zero.

4. Do the following operation k times.

if miller(n, d) == false

return false

5.return true


The following function is performed for each of the k trials. It returns true if n is most likely prime and false if n is composite and the value of d is such that d*2r = n-1 for some r>=1 and d is odd. 

bool miller( n, d)

  1. Generate a random number 'a'. The value of a lies between [2, n-2].
  2. Calculate: x = pow(a, d) % n
  3. If x == n-1 or x == 1, return true.
  4. Do the following while d != n-1. /* this loop will run for r-1 times.*/

a. x = (x*x) % n.

b. If (x == n-1) return true.

c. If (x == 1) return false.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Implementation

C++

Following is the C++ implementation of the Rabin-Miller algorithm. 

#include <bits/stdc++.h>
using namespace std;

/* power function using modulo exponentiation */
int pow(int x, unsigned int d, int t){
    /* initializing result variable*/
    int res = 1;

    /* updating the value of x if it is more than t */
    x = x % t;

    while (d > 0){
        /* multiply x with result if d is odd */
        if (d & 1){
            res = (res*x) % t;
        }

        /*The value of d must be even*/
        d = d>>1; 
        x = (x*x) % t;
    }
    return res;
}


bool MillerRabin(int d, int n){
    /* picking random number in [2, n-2] */
    int a = 2 + rand() % (n - 4);

    /* Computing a^d % n */
    int x = pow(a, d, n);

    if ( x == n-1 || x == 1) return true;

    /* Continue squaring x until one of the following occurs. */
    while (d != n-1){
        x = (x * x) % n;
        d *= 2;
        if (x == n-1) return true;
        if (x == 1)  return false;
    }

    /* returning composite */ 
    return false;
}

bool getPrimes(int n, int k){
    /* handling corner cases */
    if (n <= 3) return true;
    if (n <= 1 || n == 4) return false;

    int d = n - 1;
    while (d % 2 == 0){
        d /= 2;
    }

    /* iterating the given number of 'k' times */
    for (int i = 0; i < k; i++){
        if (!MillerRabin(d, n)){
            return false;
        }
    }

    return true;
}

/* main program */
int main(){
    /* number of iterations */
    int k = 4;

    cout << "Prime numbers less than 70: \n";
    for (int n = 1; n < 70; n++){
        if (getPrimes(n, k)){
            cout << n << " ";
        }
    }
    return 0;
}

Java

Following is the Java implementation of the Rabin-Miller algorithm. 

import java.util.*;
class BytetoString {
	static int pow(int x, int d, int t) {
 	
 		/* initializing result variable*/
 		int res = 1; 
 		
 		/* updating the value of x if it is more than t */
 		x = x % t;
 		while (d > 0)
    		{
        		/* multiply x with result if d is odd */
        		if ( (d & 1) == 1 ){
            		res = (res*x) % t;
        		}
        		/*The value of d must be even*/
        		d = d>>1; 
        		x = (x*x) % t;
    		}
 		return res;
	}

	static boolean MillerRabin(int d, int n) {
 	
 		/* picking random number in [2, n-2] */
 		int a = 2 + (int)(Math.random() % (n - 4));

 		/* Computing a^d % n */
 		int x = pow(a, d, n);

 		if (x == n - 1 || x == 1){
  			return true;
 		}

 		/* Continue squaring x until one of the following occurs. */
 		while (d != n - 1) {
  			x = (x * x) % n;
  			d *= 2;
 			
  			if (x == n - 1){
   				return true;
  			}
  			if (x == 1){
   				return false;
  			}
 		}

 		/* returning composite */ 
 		return false;
	}

	static boolean getPrimes(int n, int k) {
 	
 		/* handling corner cases */
 		if (n <= 3){
  			return true;
 		}
 		if (n <= 1 || n == 4){
  			return false;
 		}

 		int d = n - 1;
 		
 		while (d % 2 == 0){
  			d /= 2;
 		}

 		/* iterating the given number of 'k' times */
 		for (int i = 0; i < k; i++){
  			if (!MillerRabin(d, n)){
   				return false;
  			}
 		}

 		return true;
	}

	/* main program */
	public static void main(String args[]) {
 	
 		/* number of iterations */
 		int k = 4;

 		System.out.println("Prime numbers less than 70: ");
       		
 		for (int n = 1; n < 70; n++){
  			if (getPrimes(n, k)){
   				System.out.print(n + " ");
  			}
 		}
	}
}

Python

Following is the Python implementation of the Rabin-Miller algorithm. 

import random

def pow(x, d, t):
    
    """initializing result variable"""
    res = 1;
    
    """updating the value of x if it is more than t""" 
    x = x % t;
    while (d > 0):
        
        """multiply x with result if d is odd"""
        if (d & 1):
            res = (res * x) % t;
 
        """The value of d must be even"""
        d = d>>1;
        x = (x * x) % t;
    
    return res;
 

def MillerRabin(d, n):
    
    """picking random number in [2, n-2]"""
    a = 2 + random.randint(1, n - 4);
 
    """Computing a^d % n"""
    x = pow(a, d, n);
 
    if (x == n - 1 or x == 1):
        return True;
 
    """Continue squaring x until one of the following occurs."""
    while (d != n - 1):
        x = (x * x) % n;
        d *= 2;
 
        if (x == n - 1):
            return True;

        if (x == 1):
            return False;
 
    """returning composite"""
    return False;
 

def getPrimes( n, k):
    
    """handling corner cases"""
    if (n <= 3):
        return True;

    if (n <= 1 or n == 4):
        return False;

    d = n - 1;
    while (d % 2 == 0):
        d //= 2;
 
    """iterating the given number of 'k' times"""
    for i in range(k):
        if (MillerRabin(d, n) == False):
            return False;
 
    return True;
 
"""main program"""
k = 4;
 
print("Prime numbers less than 70: ");
for n in range(1,70):
    if (getPrimes(n, k)):
        print(n , end=" ");

Output

Prime numbers less than 70: 
1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67

Complexity

Time Complexity: The time complexity for the above algorithm is O(k*log(n)).

Space Complexity: The space complexity for the above algorithm is O(1).

Important Facts

  • According to Fermat's theorem, if n is a prime integer, then for every a, an-1%n = 1, 1 <= a < n.
  • Base cases ensure that n is an odd number. When n is an odd number, n-1 must be an even number. And an even number is expressed as d*2s, where d is an odd number, and s is greater than zero.
  • Based on the last two points, the value of ad*2r%n must be equal to 1, for any randomly chosen number in the range [2, n-2] must be 1.
  • If 'x2% n = 1 or (x2 - 1)% n = 0 or (x-1)(x+1)% n = 0,' then Euclid's Lemma holds. Then, for n to be prime, n divides either (x-1) or (x+1). That is, either x% n = 1 or x% n = -1.
  • Therefore from point number two and three, we can conclude that:
     
n is prime, if
    ad%n == 1 
         OR 
    ad*2i%n == -1 
    the value of i lies between 0 to r-1.

Frequently Asked Questions

What is the RSA algorithm in cryptography?

The RSA algorithm (Rivest-Shamir-Adleman) is the foundation of a cryptosystem, which is a collection of cryptographic algorithms used for certain security services or objectives.

What is the full form of RSA and AES?

AES stands for Advanced Encryption Standard, and RSA is for Rivest, Shamir, and Adleman.

What is the time complexity for the Miller-Rabin test?

The time complexity of the test is O(klogn).

Where is the Miller-Rabin test used?

High numbers can be tested for primality using this algorithm. The Miller-Rabin test will be the test of choice for many cryptographic applications due to its speed advantage over alternative primality tests.

What is cryptography?

The use of codes to secure information and communications in such a way that only the intended receiver can decipher and process them is known as cryptography.

Conclusion

In this article, we have learned about the Miller-Rabin algorithm. Also, we have seen the implementation of the Miller-Rabin algorithm in C++ and Java. Hope you like this article.

If you want to explore more, here are some related articles - 


You may refer to our Guided Path on Code Studios for enhancing your skill set on DSACompetitive ProgrammingSystem Design, etc. Check out essential interview questions, practice our available mock tests, look at the interview bundle for interview preparations, and so much more!
Happy Learning, Ninjas!

Previous article
What is Solovay-Strassen Algorithm?
Next article
What is Square Roots Modulo?
Live masterclass