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;
}
You can also try this code with Online C++ Compiler
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 + " ");
}
}
}
}
You can also try this code with Online Java Compiler
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=" ");
You can also try this code with Online Python Compiler
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 DSA, Competitive Programming, System 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!
34+ registered 
