Fermat Primality Test | Baeldung on Computer Science

1. Introduction

Prime numbers have had the attention of mathematicians for centuries. Today, they have a crucial role in computer science and cryptography.

The trivial way to determine if a number $n$ is prime is to check whether it is divisible by a number between 2 and $n$ . But, this brute force method is not computationally efficient.

Sieve of Eratosthenes is a more optimized way to determine prime numbers, which is known since ancient times. Also, there are more efficient ways to determine whether a number is prime. Still, these methods are costly. In some cases, we can use pseudoprimes instead.

In this tutorial, we’ll learn about Fermat’s little theorem and Fermat primality test. We can use this test to identify some non-prime numbers quickly.

2. Fermat’s Little Theorem

Fermat suggested that, if a number $\mathbf{n}$ is prime, then the following equality holds for any number $\mathbf{a}$ in the range $\mathbf{[1, n-1]}$ :

$\mathbf{a^{n-1} \equiv 1 \boldsymbol{\pmod{n}}}$

In the equation above, mod operator represents the modulo operation. We read it as $a^{n-1}$ is conjugate to 1 in modulo $n$ . Hence, $a^{n-1}$ has a remainder of 1 when divided by $n$ .

If this equality doesn’t hold for any $a$ value, then $n$ is a composite number. For example, to test if 23 is a prime number, we need to calculate

$a^{22} \equiv 1 \pmod{23}$

for different values of $a$ . Let’s choose $a$ = 2 for starters:

$2^{22} = 4194,304 \equiv 1 \pmod{23}$

Let’s try another number. This time we choose $a$ = 9:

$9^{22} \equiv 1 \pmod{23}$

Trying different values for $a$ will not change the result in this case. We’ll always get the 22nd power of $a$ to be equivalent to 1 in modulus 23.

However, there are many examples where equality holds for all possible $\mathbf{a}$ values, but $\mathbf{n}$ is not a prime number. For instance, the number 561 passes the Fermat test. In other words, we can’t find any value $a$ such that:

$a^{560} \equiv 1 \pmod{561}$

Yet 561 is a composite number, as $3 \times 11 \times 17 = 561$ . Such numbers passing the Fermat test even though being composite are called Carmichael numbers.

Despite the existence of Carmichael numbers, Fermat’s test is still used to determine if a number is possibly prime or not. For a large number $n$ , we try some random $a$ values and conclude it is a pseudoprime if it passes the test.

3. Fermat Primality Test

Implementing a primality test using Fermat’s little theorem is trivial.

Still, we can’t check if the equality above holds for any value of $\mathbf{a}$ . This would lead to a very inefficient algorithm. Instead, we try some random values and conclude if we can’t find a counter-example amongst them:

We iterate for $k$ different random integers. Clearly, the choice of $k$ affects the overall runtime of the algorithm. How we calculate the residual of the exponentiation operation determines the overall running time complexity.

The trivial way to compute $a^{n-1} \pmod{n}$ includes $n$ multiplication operations to calculate the exponent and a division operation to find the remainder. Instead, we can compute the result more efficiently by binary exponentiation:

Computing $a \times a \pmod{n}$ has a complexity of $\mathcal{O}(\log^2 n)$ . We apply the modular multiplication operation for approximately $\log n$ times to compute $a^{n-1}$ by modular exponentiation. In this method, we calculate the residual in each iteration after calculating its square modulo $n$ .

Hence, the complexity to compute the residual $a^{n-1} \pmod{n}$ is $\mathcal{O}(\log^2 n \times \log n)$ .

As a result, the running time of Fermat algorithm is $\boldsymbol{\mathcal{O}}(\mathbf{k \times} \boldsymbol{\log} \mathbf{^2 n \times \boldsymbol{\log} n) = \boldsymbol{\mathcal{O}}(k \boldsymbol{\log}^2 n)}$ .

4. Implementation

We can easily code the Fermat primality test in a programming language like Java.

For better performance, we need to cover some edge cases and use modular exponentiation instead of the built-in power function:

public class FPT {

    static int mPower(int x, int e, int m) {
        int res = 1;

        while (e > 0) {
            if ((e % 2) == 1) {
                res = (res * x) % m;
                e--;
            } else {
                x = (x * x) % m;
                e = e / 2;
            }
        }
        return res;
    }

    static boolean isPrime(int n, int k) {
        if (n % 2 == 0 && n != 2)  {
            return false;
        }

        if (n <= 3)  {
            return true;
        }

        while (k > 0) {
            int a = (int) Math.random() * (n - 3) + 2;
            if (mPower(a, n - 1, n) != 1) {
                return false;
            }

            k--;
        }

        return true;
    }
}

5. Conclusion

In this article, we’ve covered Fermat’s little theorem and Fermat primality test.

We’ve emphasized that some numbers can pass all cases of the Fermat primality test, even though they are not prime. In addition, as we only try $k$ random numbers, we might miss finding a counter-example. This test isn’t guaranteed to detect a composite number.

The Fermat test is applicable when we need to scan some numbers to improve performance quickly. For example, the key generation phase of public-key cryptography algorithms can benefit from fast prime number screening.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex

1. Introduction

2. Fermat’s Little Theorem

3. Fermat Primality Test

4. Implementation

5. Conclusion