Types of Primality Testing
Primality tests can be classified into the following categories:
Deterministic Algorithm
Deterministic algorithms accept an integer and it gives the result as either a prime or a composite. A correct result is always given by this method.
Divisibility Algorithm
The divisibility algorithm is considered the simplest primality test, and the test looks like this:
The algorithm checks whether any integer between 2 and n- 1 divides the input number n. If any number n is divisible by m, then n is composite; otherwise, n is a prime. However, it is only crucial to test m up to √n and not all m up to n – 1. n can be factored into two values, at least one of which must be smaller than or equal to √n if n is a composite number.
Probabilistic Algorithm
A probabilistic algorithm provides a response that is correct most of the time, but only sometimes. These tests determine if n meets one or more requirements that all primes should meet. The following guidelines determine which of a prime or a composite a probabilistic algorithm will restore:
- The procedure will return a prime if the integer under test is, in fact, a prime.
- It can return a prime with probability Ɛ(refers to a term in statistics/regression which denotes an arbitrarily small, positive number), but if the input integer is a composite, it will return a composite with probability 1-Ɛ. If the procedure is performed "m" times, the chance of error can be increased while the probability of error is reduced to Σm.
Fermat Primality Test
Fermat's Little Theorem states that if n is prime, an-1 ≡ 1 (mod n) is the foundation of the Fermat Primality Test. If an input n and a<n, it can determine whether an-1 ≡ 1 (mod n). This method always returns true if a provided number is a prime. It may return true or false depending on whether the input integer is composite (or non-prime). The probability of inaccurate results for composite is low and can be decreased by performing additional iterations. Because too many composites are probably prime, the test has a high error cost.
If n is a prime number, and for every a, 1 < a < n, we do the following to check if n is prime.
an-1 ≡ 1 (mod n)
OR
an-1 % n = 1
Let’s see examples for a better understanding of this test.
For example:
Example 1: let’s take n=5 (prime number)
Since 1<a<n, the values of a can be 2,3,4. So let’s check for the three numbers.
24 ≡ 1 (mod 5) [or 24 %5 = 1],
34 ≡ 1 (mod 5) [or 34 %5 = 1]
44 ≡ 1 (mod 5) [or 44 %5 = 1]
Example 2: let’s take n=11 (prime number)
Since 1<a<n, the values of ‘a’ can be 2,3,4,5,6,7,8,9,10. So let’s check for these numbers.
210 ≡ 1 (mod 11) [or 210 % 11 = 1],
310 ≡ 1 (mod 11) [or 310 % 11 = 1]
410 ≡ 1 (mod 11) [or 410 % 11 = 1]
510 ≡ 1 (mod 11) [or 510 % 11 = 1]
610 ≡ 1 (mod 11) [or 610 % 11 = 1]
710 ≡ 1 (mod 11) [or 710 % 11 = 1]
810 ≡ 1 (mod 11) [or 810 % 11 = 1]
910 ≡ 1 (mod 11) [or 910 % 11 = 1]
1010 ≡ 1 (mod 11) [or 1010 % 11 = 1]
Algorithm for Fermat Primality Test
- for i from 1 to k: Choose a = random(2, n-1) /*choose a random number between 2 and n-1*/
- If gcd(a, n) ≠ 1, then return false.
- If an-1 ≢ 1 (mod n), then return false.
- If steps 2 and 3 fail, then return true which means the number is probably prime.
C++ Code for Fermat Primality Test
#include <bits/stdc++.h>
using namespace std;
/* calculate (a^n)%m */
int calculate(int a, int n, int m){
int ans = 1;
/* do the following if a>=m*/
a = a % m;
while (n > 0){
if (n %2 != 0)
ans = (ans*a) % m;
/* n has now become even */
n = n/2;
a = (a*a) % m;
}
return ans;
}
int gcd(int n1, int n2){
if(n1 < n2)
return gcd(n2, n1);
else if(n1 % n2 == 0)
return n2;
else return gcd(n2, n1 % n2);
}
/* More the value of k, the better the results of primality test*/
bool isPrime(int n, int k){
/* Base cases cover the cases where n<4 */
if (n <= 1 || n == 4)
return false;
if (n <= 3)
return true;
while (k-- >0){
/* Choose random number in the range [2..n-2] */
int a = 2 + rand() % (n-4);
/*Checking if a and n are co-prime by calculating their greatest common divisor(gcd) */
if (gcd(n, a) != 1)
return false;
/* Fermat's primality test */
if (calculate(a, n-1, n) != 1)
return false;
}
/* If we have reached here, this means the number is prime */
return true;
}
int main(){
int k = 5;
isPrime(5, k)? cout << "True\n": cout << "False\n";
isPrime(11, k)? cout << "True\n": cout << "False\n";
isPrime(21, k)? cout << "True\n": cout << "False\n";
return 0;
}
You can also try this code with Online C++ Compiler
Run Code
Output:
True
True
False
Java Code for Fermat Primality Test
import java.io.*;
import java.math.*;
class Main {
static int calculate(int a,int n, int m){
int ans = 1;
/* do the following if a>=m*/
a = a % m;
while (n > 0){
if (n %2 !=0)
ans = (ans*a) % m;
/* n has now become even */
n = n/2;
a = (a*a) % m;
}
return ans;
}
/* More the value of k, the better the results of primality test*/
static boolean isPrime(int n, int k){
/* Base cases cover the cases where n<4 */
if (n <= 1 || n == 4)
return false;
if (n <= 3)
return true;
while (k-- > 0){
/* Choose random number in the range [2..n-2] */
int a = 2 + (int)(Math.random() % (n - 4));
/* Fermat's primality test */
if (calculate(a, n-1, n) != 1)
return false;
}
/* If we have reached here, this means the number is prime */
return true;
}
public static void main(String args[]){
int k = 5;
if(isPrime(5, k))
System.out.println("True");
else
System.out.println("False");
if(isPrime(11, k))
System.out.println("True");
else
System.out.println("False");
if(isPrime(21, k))
System.out.println("True");
else
System.out.println("False");
}
}
You can also try this code with Online Java Compiler
Run Code
Output:
True
True
False
Python Code for Fermat Primality Test
import random
def calculate(a, n, m):
ans= 1
#do the following if a>=m
a = a % m
while n > 0:
if n % 2:
ans = (ans * a) % m
n = n - 1
else:
a = (a ** 2) % m
#n has now become even
n = n // 2
return ans % m
#More the value of k, the better the results of primality test
def isPrime(n, k):
#Base cases cover the cases where n<4
if n == 1 or n == 4:
return False
elif n == 2 or n == 3:
return True
else:
for i in range(k):
#Choose random number in the range [2..n-2]
a = random.randint(2, n - 2)
# Fermat's primality test
if calculate(a, n - 1, n) != 1:
return False
#If we have reached here, this means the number is prime
return True
k = 5
if isPrime(5, k):
print("True")
else:
print("False")
if isPrime(11, k):
print("True")
else:
print("False")
if isPrime(21, k):
print("True")
else:
print("False")
You can also try this code with Online Python Compiler
Run Code
Output:
True
True
False
Time complexity: O(klog n)
Auxiliary space: O(1)
We hope you have learned everything about the primality test.
Frequently Asked Questions
What is a primality test?
A primality test is used to determine whether an input integer is prime. these tests can sometimes be deterministic. They are perfect for deciding if a number is prime or composite.
How many types of primality tests are there?
There are four types- deterministic, divisibility, probabilistic, and fermat primality test.
What is the time complexity for the fermat primality test?
The time complexity of the test is O(klogn).
Where is the primality test used?
The primality test is helpful in cryptography.
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 explored the primality test. We explored different types of primality tests. We also studied the fermat primality test. To learn more about articles like primality test, check out more articles on cryptography as follows
Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, System Design, Competitive Programming, JavaScript, etc. Enroll in our courses and refer to the problems available and mock tests. Take a look at the interview bundle and interview experiences for placement preparations.
Happy Learning Ninja!