Prime numbers are very important in Cryptography. It is for that reason that you will have to study some methods for testing whether a given number is prime or not (a.k.a. primality tests). One of such methods is the Miller-Rabin Test.
A number n is prime if and only if it has only two divisors, 1 and itself. If you find one number that is a divisor of n, then n is not prime.
The simplest algorithm to test whether a number is prime or not can be described as follows:
input: n
for i=2, i<n
if (n mod 2==0)
return not prime
return prime
The previous algorithm works. However, it is not efficient. Instead of checking all the numbers until n-1, we could check until the square root of n plus 1. In this way, it will be less inefficient.
The problem with this algorithm is that when we use big prime numbers, it takes too much time and, in Cryptography, we need big prime numbers.
For this reason, we need to use a different algorithm, one that is efficient when testing big prime numbers.
Miller-Rabin Test
The Miller-Rabin test is an easy-to-use efficient algorithm to test if a number is prime or not.
It is a probabilistic algorithm. This means that if the test returns that the number is prime, there is a certain probability (although very low) that the number is not prime.
If in your case you need to be 100% sure that the number is prime, then this test is not the one you should use.
Input: odd integer n>=3
1- find u odd and k so that n-1 = u * s^k
2- Choose a randomly, where 1<a<n-1
3- b = a^u mod n
4- if b==1 or b== n-1 return probable prime
5- repeat k-1 times
6- b = b^2 mod n
7- if b=n-1 return probably prime
8- if b=1 return not prime
9- return not prime
I won’t go deeper into the mathematical background used to create the previous algorithm. However, if you want to read more about it you can read section 3.4 Primality Testing of the book An Introduction to Mathematical Cryptography by Hoffstein et al.
Because this is a probabilistic test, it is recommended to run the test several times.
Let’s see the python implementation of this algorithm.
Python implementation for a single round
"""
n>=3
"""
def miller_rabin(n):
if n<=3:
raise Exception('n should b greater than 3.')
if n % 2 == 0:
return False
# Find u odd such that n-1 = 2^k * u
u = n - 1
k = 0
while (u % 2 == 0):
u //= 2
k+=1
#Let a be randomly chosen from {2,...,n − 2};
a = random.randint(2,n-2)
# b = a^u mod n
b = pow(a,u,n)
if b==1 or b ==n-1:
return True
for _ in range (1,k-1):
b= (b*b) % n
if b==n-1: return True
if b==1:
return False
return False
The previous one is the implementation for one round of the Miller-Rabin test.
Find below a similar implementation, but in this case, we can use several rounds of the test.
Python implementation for a multiple round
import random
"""
n>=3
test using q rounds
"""
def miller_rabin_qrounds(n, q):
if n<=3:
raise Exception('n should b greater than 3.')
if n % 2 == 0:
return False
# Find u odd such that n-1 = 2^k * u
u = n - 1
k = 0
while (u % 2 == 0):
u //= 2
k+=1
for _ in range(q):
#Let a be randomly chosen from {2,...,n − 2};
a = random.randint(2,n-2)
# b = a^u mod n
b = pow(a,u,n)
if b==1 or b ==n-1:
continue
for _ in range (k-1):
b= (b*b) % n
if b==n-1: break
else:
return False
return True
Comparison of the Miller-Rabin test
To show you the usefulness of the Miller-Rabin test when testing for big prime numbers, I created another function that uses the common algorithm that tells us (100% accuracy) if a number is prime or not.
def prime(n):
if n==2: return True
for i in range(2, int(n**0.5)+1):
if n % i == 0:
return False
return True
This function is optimized to search only until the square root of the number plus 1.
See the program below for a prime number with 17 digits.
if __name__=='__main__':
number = 75776624669700389
start_time = time.time()
print( miller_rabin_qrounds(number, 10) )
print("--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
print ( prime(number) )
print("--- %s seconds ---" % (time.time() - start_time))
As you can see, I’ll print the execution time for both algorithms. In the case if the Miller-Rabin test, I’m using 10 rounds.
See the results below.
As you can see, the runtime difference is big enough to be considered relevant.
You can try the algorithm with a bigger prime number. If the prime number is big enough, you will have to wait days to get a result from the second algorithm. Don’t believe me, just try it out yourself.
Remember that this difference is important when you are testing prime numbers.
Conclusions
The Miller-Rabin test is very important when we want to know if a big number is a prime or not and we don’t need to be 100% sure of it.
For a small number, you can still use the algorithm that will give you 100% accuracy instead of the Miller-Rabin test.
Related posts: