费马素性测试

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 is prime is to check whether it is divisible by a number between 2 and . 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 is prime, then the following equality holds for any number in the range :

   

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

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

   

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

   

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

   

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

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

   

Yet 561 is a composite number, as . 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 , we try some random 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.

till, we can’t check if the equality above holds for any value of . 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:

algorithm IsPrime(n, k):
    // INPUT
    //    n = number to be tested for primality
    //    k = number of times the test will be repeated
    // OUTPUT
    //    Returns "Composite" if n is found to be composite, 
    //    "Pseudoprime" otherwise
    i <- 1
    while i <= k:
        a <- uniform random number between 2 and n - 1
        
        if a^(n - 1) != 1 (mod n):
            return "Composite"
        
        i <- i + 1
    
    return "Pseudoprime"

We iterate for different random integers. Clearly, the choice of 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 includes 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:

algorithm Power(x, e, m):
    // INPUT
    //    x = exponentiation base
    //    e = exponent
    //    m = modular operand
    // OUTPUT
    //    Returns the residual of x^e mod m
    result <- 1
    while e > 0:
        if e is odd:
            result <- (result * x) mod m
            e <- e - 1
        else:
            x <- (x * x) mod m
            e <- e / 2
    
    return result

Computing has a complexity of . We apply the modular multiplication operation for approximately times to compute by modular exponentiation. In this method, we calculate the residual in each iteration after calculating its square modulo .

Hence, the complexity to compute the residual is .

As a result, the running time of Fermat algorithm is .

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 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.