## 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, a^{n-1 }≡ 1 (mod n) is the foundation of the Fermat Primality Test. If an input n and a<n, it can determine whether a^{n-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.

a^{n-1 }≡ 1 (mod n)

OR

a^{n-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.

2^{4} ≡ 1 (mod 5) [or 2^{4 }%5 = 1],

3^{4} ≡ 1 (mod 5) [or 3^{4 }%5 = 1]

4^{4} ≡ 1 (mod 5) [or 4^{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.

2^{10} ≡ 1 (mod 11) [or 2^{10 }% 11 = 1],

3^{10} ≡ 1 (mod 11) [or 3^{10 }% 11 = 1]

4^{10} ≡ 1 (mod 11) [or 4^{10 }% 11 = 1]

5^{10} ≡ 1 (mod 11) [or 5^{10 }% 11 = 1]

6^{10} ≡ 1 (mod 11) [or 6^{10 }% 11 = 1]

7^{10} ≡ 1 (mod 11) [or 7^{10 }% 11 = 1]

8^{10 }≡ 1 (mod 11) [or 8^{10 }% 11 = 1]

9^{10 }≡ 1 (mod 11) [or 9^{10 }% 11 = 1]

10^{10 }≡ 1 (mod 11) [or 10^{10 }% 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 a
^{n-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;
}
```

**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");
}
}
```

**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")
```

**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!