Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Primality Testing?
3.
Types of Primality Testing
3.1.
Deterministic Algorithm
3.2.
Divisibility Algorithm
3.3.
Probabilistic Algorithm
3.4.
Fermat Primality Test
3.4.1.
Algorithm for Fermat Primality Test
3.4.2.
C++ Code for Fermat Primality Test
3.4.3.
Java Code for Fermat Primality Test
3.4.4.
Python Code for Fermat Primality Test
4.
Frequently Asked Questions
4.1.
What is a primality test?
4.2.
How many types of primality tests are there?
4.3.
What is the time complexity for the fermat primality test?
4.4.
Where is the primality test used?
4.5.
What is cryptography?
5.
Conclusion
Last Updated: Mar 27, 2024
Hard

What is Primality testing?

Author Aashna Luthra
0 upvote

Introduction

Welcome Ninjas! Do you want to know what test can help in determining whether an input integer is prime?  Primality testing is used for this purpose. Are you interested in knowing more about primality testing? Great! You are at the right place.

intro image

In this blog, we will cover essential aspects of primality testing. We will also study types of primality testing.

What is Primality Testing?

A primality test is used to determine whether an input integer is prime. Primality tests can sometimes be deterministic. They are perfect for deciding if a number is prime or composite. Prime numbers are helpful in cryptography. 

A prime number with a key typically larger than 1024 bits is required to give enhanced security by the RSA algorithm, which is one of the main cryptosystems. Working with such large numbers is difficult, especially when the primality test is conducted when the operations are / and %. As a result, the best algorithms for testing for primality can only determine whether a given number is a "probable prime" or composite.

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 2%5 = 1],

34 ≡ 1 (mod 5) [or 3%5 = 1]

44 ≡ 1 (mod 5) [or 4%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

  1. for i from 1 to k: Choose a = random(2, n-1) /*choose a random number between 2 and n-1*/
  2. If gcd(a, n) ≠ 1, then return false. 
  3. If an-1 ≢ 1 (mod n), then return false.
  4. 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!

Live masterclass