Fermat Primality Test

The Fermat primality test is a probabilistic test for determining whether a number is composite or probably prime. Named after Pierre de Fermat, it's based on Fermat's Little Theorem and provides a fast but not completely reliable method for prime testing.

Mathematical Foundation

Fermat's Little Theorem states that if p is prime and a is not divisible by p, then:

The Fermat test uses this as follows: for a number n that we want to test for primality, we choose a random number a (called the base) where 1 < a < n. If:

then n is definitely composite. If the congruence holds, n is probably prime, and we call n a probable prime to base a.

Time and Space Complexity

For a single test with one base a, the time complexity using fast modular exponentiation is:

The space complexity is:

JavaScript Implementation

Here's an implementation of the Fermat primality test:

code.js
1function modPow(base, exponent, modulus) {
2    if (modulus === 1) return 0;
3    
4    let result = 1;
5    base = base % modulus;
6    
7    while (exponent > 0) {
8        if (exponent % 2 === 1) {
9            result = (result * base) % modulus;
10        }
11        base = (base * base) % modulus;
12        exponent = Math.floor(exponent / 2);
13    }
14    
15    return result;
16}
17
18function fermatTest(n, k = 5) {
19    // Handle small numbers and even numbers
20    if (n <= 1 || n === 4) return false;
21    if (n <= 3) return true;
22    if (n % 2 === 0) return false;
23    
24    // Perform k tests
25    for (let i = 0; i < k; i++) {
26        // Generate random base a where 2 <= a <= n-2
27        const a = 2 + Math.floor(Math.random() * (n - 3));
28        
29        // If a^(n-1) mod n != 1, n is composite
30        if (modPow(a, n - 1, n) !== 1) {
31            return false;
32        }
33    }
34    
35    return true; // Probably prime
36}
37
38// Example usage:
39console.log(fermatTest(17));  // true
40console.log(fermatTest(24));  // false

Carmichael Numbers and Limitations

The main limitation of the Fermat test is the existence of Carmichael numbers. These are composite numbers that pass the Fermat test for all coprime bases. The smallest Carmichael number is 561.

Here's a function to check if a number is a Carmichael number:

code.js
1function isCarmichael(n) {
2    if (n < 561 || n % 2 === 0) return false;
3    
4    // Get prime factors
5    const factors = [];
6    let temp = n;
7    for (let i = 2; i * i <= temp; i++) {
8        if (temp % i === 0) {
9            factors.push(i);
10            while (temp % i === 0) {
11                temp /= i;
12            }
13        }
14    }
15    if (temp > 1) factors.push(temp);
16    
17    // Check Carmichael conditions
18    if (factors.length < 3) return false;
19    
20    // Check if n-1 is divisible by p-1 for all prime factors p
21    return factors.every(p => (n - 1) % (p - 1) === 0);
22}

Strong Pseudoprime Test

To address the Carmichael number weakness, we can use a stronger version of the Fermat test:

code.js
1function strongPseudoprimeTest(n, a) {
2    if (n <= 1) return false;
3    if (n === 2) return true;
4    if (n % 2 === 0) return false;
5    
6    // Write n-1 as d * 2^s
7    let s = 0;
8    let d = n - 1;
9    while (d % 2 === 0) {
10        s++;
11        d = Math.floor(d / 2);
12    }
13    
14    // Compute a^d mod n
15    let x = modPow(a, d, n);
16    if (x === 1 || x === n - 1) return true;
17    
18    // Square x up to s-1 times
19    for (let r = 1; r < s; r++) {
20        x = (x * x) % n;
21        if (x === n - 1) return true;
22        if (x === 1) return false;
23    }
24    
25    return false;
26}

Applications

The Fermat primality test is useful in several contexts:

1. Quick primality testing for non-critical applications
2. Generation of probable primes for cryptographic purposes (when combined with other tests)
3. Educational purposes to understand probabilistic algorithms
4. Initial screening before more rigorous primality tests

Best Practices

When using the Fermat test:

1. Always use multiple bases to increase confidence
2. Consider combining with other tests (like Miller-Rabin) for higher reliability
3. Be aware of Carmichael numbers
4. Use strong pseudoprime testing for better reliability

Limitations

1. Cannot definitively prove primality
2. Vulnerable to Carmichael numbers
3. May give false positives (composite numbers that pass the test)
4. Requires good random number generation for base selection

For cryptographic applications, the Miller-Rabin test is generally preferred as it provides better guarantees against false positives.