Primality Test

What is Primality Test?

The Primality test is an algorithm for determining whether a given positive integer is a prime number or not.

The primality of a number can also be checked by determining whether it is a composite number or not, because if the number is not a composite number nor 1, then it must be a prime number.

Example

Source Code - C++17

Source Code - Java (1.8)

Source Code - Python 3

The output is the same for all of the implementations as they peform the same thing, the only difference being the programming language.

Output

In the above examples, we are checking whether the given number is a prime number or not, to do so, we are iterating from $2$ to $n-1$ to check if these numbers divide the given number. If they do, then the given number is not a prime number, else it is a prime number.

School method

The school method is a simple solution that comes first to everyone's mind for primality check as it is the simplest of all.

In the School Method algorithm, we iterate through all the numbers from $2$ to $n-1$ (the number to be checked is $n$) and check if they divide the number $n$.

Complexity Analysis

Time Complexity: $O(N)$

The time complexity of the School Method primality check is $O(N)$ as we iterate $N-2$ times.

Space Complexity: $O(1)$

The space complexity here is constant.

The algorithm in the example above is School Method only.

Optimized School Method

In the School Method, we can do some optimizations like:

• Instead of checking till $n$, we will check till $\sqrt{n}$ because a factor of $n$ larger than $\sqrt{n}$ must be a multiple of a number smaller than $\sqrt{n}$ that has been already checked and should not be checked again.
• We will first check the divisibility of $n$ by $2$ and $3$, then check its divisibility by numbers of the form $6k-1$ and $6k+1$ starting at $k=1$. We do so because any integer greater than $4$ can be expressed in the form of $6k-1$, $6k$, $6k+1$, $6k+2$, $6k+3$, and $6k+4$ (for $k>0$), but integers of the form $6k$, $6k+2$, $6k+3$, and $6k+4$ will be divisible by $2$ or $3$.

Let's have a look at its implementation in the section below.

Implementation of the Optimized School Method

Source Code - C++17

Source Code - Java (1.8)

Source Code - Python 3

The output is the same for all of the implementations as they peform the same thing, the only difference being the programming language.

Output

In the above examples, we are checking whether the given number is a prime number or not, to do so, we are first checking its divisibility by $2$ and $3$, then checking its divisibility by numbers of the form $6k-1$ and $6k+1$. If the given number is divisible by any number then it is not a prime number, else it is.

Complexity Analysis

Time complexity: $O(\sqrt{N})$

The asymptotic time complexity of the Optimized School Method primality check is $O(\sqrt{N})$ because we iterate $\sqrt{N}/6$ ($i+=6$ in the for loop) times in this algorithm.

Space Complexity: $O(1)$

The space complexity here is constant.

Trial Division Method

The Trial Division Method is a primality check algorithm in which we accept some integer $n$, check if any number from 2 to $\sqrt{n}$ divides the given integer, if a divisor is found then $n$ is a composite number, otherwise, it is a prime number. It is very similar to the school method.

Complexity Analysis

Time complexity: $O(\sqrt{N})$

The time complexity of The Trial Division primality check is $O(\sqrt{N})$ as we iterate $\sqrt{N}-1$ times.

Space Complexity: $O(1)$

The space complexity here is constant.

Fermat Primality Test

The Fermat Primality test is a probabilistic method to determine whether the given integer is a probable prime number or not.

It is based on Fermat's Little Theorem that states if $p$ is a prime number and $a$ is not divisible by $p$, then $a^{p-1} \equiv 1\;(mod\;p)$, i.e $a^{p-1} = k*p + 1$ (where $k$ is an integer constant).

If we want to test $p$ for a prime number, then we will pick some random integers $a$ that are not divisible by $p$ and see whether the congruency holds or not. If the congruency doesn't hold for a value of $a$, then it will be a proof that $p$ is a composite number, but if the congruency holds for more than one values of $a$, then $p$ is a probable prime number.

Algorithm Steps

• Repeat the following $k$ times (higher value of $k$ indicates higher probability of correct results):
  • Handle corner cases for $p<3$ ($p$ is the number to be tested).
  • Pick a random number $a$ in the range $1 < a < p$.
  • If $a^{p-1} \not\equiv 1\;(mod\;p)$, then return $False$.
• Return $True$, $p$ is probably a prime number.

Example

Let us assume, we have to check whether $n = 221$ is a prime number or not. We will randomly pick a number $a$ in the range $1 < a < 221$. Then we will check whether the congruency holds or not.

For $a = 38$,

$38^{221-1} \equiv 1\;(mod\;221)$, as $a^{p-1} \equiv 1\;(mod\;p)$ $=> 38^{220} \equiv 1\;(mod\;221)$,

Now there can be two cases, $221$ is a prime number, or $38$ is a Fermat liar. To proceed, let's take $a=24$.

but, $24^{220} \not\equiv 1\;(mod\;221)$, as $24^{220} \equiv 81\;(mod\;221)$.

This proves that $221$ is a composite number and $38$ is Fermat liar, $24$ being the Fermat witness for the compositeness of $221$.

Complexity Analysis

Time Complexity: $O(K*log(N))$

Here, $K$ is the number of iterations, and $N$ is the number to be tested for primality. $log(N)$ is the time complexity for computing $a^{p-1}$ and the algorithm is repeated $K$ times. So the time complexity is $O(K*log(N))$.

Space Complexity: $O(1)$

There is no need for extra space, so the space complexity is constant.

The Fermat's little theorem is used for one more Primality test, called the Miller-Rabin Primality Test.

Miller-Rabin Primality Test

The Miller-Rabin Primality Test is also a probabilistic method to determine whether the given integer is a prime number or not, similar to the Fermat Primality Test. It is also based on the Fermat's Little Theorem (discussed in the above section).

This test was discovered by Gary Lee Miller in 1976, later modified by Michael Oser Rabin in 1980.

The result of this test will be whether the given number is a composite number or a probable prime number. The probable prime numbers in the Miller-Rabin Primality Test are called strong probable numbers, as they have a higher chance of being a prime number than in the Fermat's Primality Test.

A number $n$ is said to be strong probable prime number to base $a$ if one of these congruence relations (equivalence relations in modulo arithmetics, $A \equiv B(mod\;C)$ means $A$ is congruent to $B$ modulo $C$) holds:

• $a^d \equiv 1\;(mod\;n)$
• $a^{2^{r}*d} \equiv -1\;(mod\;n)$

Algorithm Steps

$n$ is the number to be tested.

$k$ indicates the accuracy of the test.

$d$ is an odd number such that $n-1$ can be written in the form of $d*2^r$ (Since $n$ is odd, $n-1$ must be even and $r>0$).

$isPrime(int\; n, int\; k)$

• Handle base cases for $n < 3$.
• if $n$ is even, return $False$.
• Find an odd number $d$.
• Loop the following $k$ times:
  • Check if $millerTest(n, d)==false$, if yes, return $False$.
• Return $True$.

$millerRabinTest(int \;n, int \;d)$

• Pick a random number $a$ in the range $2 \leq a \leq n-2$.
• Compute KaTeX parse error: Expected 'EOF', got '%' at position 15: x = pow(a, d) %̲ n.
• Return $True$ if $x==1 \;or \;x==n-1$.
• Loop the following till $d == n-1$.
  • $x = (x*x)\%n$.
  • Return $False$ if $x==1$.
  • Return $True$ if $x==n-1$.

Implementation of the Miller-Rabin Primality Test

Source Code - C++17

Source Code - Java (1.8)

Source Code - Python 3

The output is the same for all of the implementations as they peform the same thing, the only difference being the programming language.

Output

In the above examples, we are checking whether the given number is a probable prime number or a composite number, to do so, we are using the Miller-Rabin Primality Test. If the function returns $True$, then the given number is a probable prime number, otherwise, it is a composite number.

The Miller-Rabin Test, being an extension of the Fermat's Primality Test, is more accurate than Fermat's Primality Test, thus, it is preferred over that.

Complexity Analysis

Time Complexity: $O(K*log^3(N)$

The time complexity of the Miller-Rabin Primality Test is $O(K*log^3(N)$, where $N$ is the number to be checked for primality, and $K$ is the number of iterations performed for accuracy as per the requirement.

Space Complexity: $O(1)$

There is no need for extra space, so the space complexity is constant.