Lucas-Lehmer Primality Test

The Lucas-Lehmer primality test is a deterministic primality test specifically designed for Mersenne numbers. A Mersenne number is a number of the form where is prime. The test is remarkably efficient for these numbers and is used to find some of the largest known prime numbers.

Mathematical Foundation

The Lucas-Lehmer test is based on the following theorem:

For , the Mersenne number is prime if and only if divides , where is defined by:

This leads to a surprisingly simple and efficient algorithm for testing Mersenne primes.

Time and Space Complexity

The time complexity for testing is , and the space complexity is , where is the exponent of the Mersenne number.

JavaScript Implementation

Here's an implementation of the Lucas-Lehmer test.

code.js
1function lucasLehmer(p) {
2    // Handle edge cases
3    if (p === 2) return true;  // 2^2 - 1 = 3 is prime
4    if (p <= 1) return false;
5    
6    // Calculate Mersenne number M_p = 2^p - 1
7    const mersenne = BigInt(Math.pow(2, p)) - 1n;
8    
9    // Initialize s = 4
10    let s = 4n;
11    
12    // Perform p-2 iterations
13    for (let i = 0; i < p - 2; i++) {
14        // Calculate next term: s = (s * s - 2) mod M_p
15        s = ((s * s) - 2n) % mersenne;
16        
17        // If s becomes negative, add mersenne
18        if (s < 0n) s += mersenne;
19    }
20    
21    // M_p is prime if and only if s = 0
22    return s === 0n;
23}
24
25// Example usage:
26console.log(lucasLehmer(3));   // true (2^3 - 1 = 7 is prime)
27console.log(lucasLehmer(11));  // true (2^11 - 1 = 2047 is prime)

Optimized Implementation

For larger numbers, we need more efficient modular arithmetic:

code.js
1function modMultiply(a, b, m) {
2    let result = 0n;
3    a = a % m;
4    while (b > 0n) {
5        if (b % 2n === 1n) {
6            result = (result + a) % m;
7        }
8        a = (a * 2n) % m;
9        b = b / 2n;
10    }
11    return result;
12}
13
14function optimizedLucasLehmer(p) {
15    if (p === 2) return true;
16    if (p <= 1) return false;
17    
18    // Calculate Mersenne number
19    const m = (1n << BigInt(p)) - 1n;
20    
21    // Initialize s = 4
22    let s = 4n;
23    
24    // Perform p-2 iterations with optimized arithmetic
25    for (let i = 0; i < p - 2; i++) {
26        s = modMultiply(s, s, m) - 2n;
27        if (s < 0n) s += m;
28    }
29    
30    return s === 0n;
31}

Finding Mersenne Primes

Here's a function to find Mersenne primes up to a given exponent:

code.js
1function findMersennePrimes(maxExponent) {
2    function isPrime(n) {
3        if (n <= 1) return false;
4        if (n <= 3) return true;
5        if (n % 2 === 0) return false;
6        
7        for (let i = 3; i * i <= n; i += 2) {
8            if (n % i === 0) return false;
9        }
10        return true;
11    }
12    
13    const mersennePrimes = [];
14    
15    for (let p = 2; p <= maxExponent; p++) {
16        if (isPrime(p) && lucasLehmer(p)) {
17            mersennePrimes.push({
18                exponent: p,
19                value: BigInt(Math.pow(2, p)) - 1n
20            });
21        }
22    }
23    
24    return mersennePrimes;
25}
26
27// Example usage:
28console.log(findMersennePrimes(11));

Applications

The Lucas-Lehmer test is used in several important contexts:

1. Finding large prime numbers (GIMPS project)
2. Perfect number discovery (related to Mersenne primes)
3. Cryptographic applications
4. Number theory research

Historical Significance

Mersenne primes, tested using the Lucas-Lehmer test, have led to:

1. Discovery of the largest known prime numbers
2. Advances in computer arithmetic
3. Development of distributed computing projects
4. Better understanding of prime number distribution

Performance Considerations

For optimal performance:

1. Use efficient modular arithmetic
2. Implement Montgomery reduction for large numbers
3. Use parallel processing for multiple tests
4. Optimize memory usage for large exponents

Example: Testing Known Mersenne Primes

code.js
1const knownMersennePrimeExponents = [
2    2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127
3];
4
5function testKnownMersennePrimes() {
6    const results = knownMersennePrimeExponents.map(p => ({
7        exponent: p,
8        isPrime: lucasLehmer(p),
9        value: `2^${p} - 1`
10    }));
11    
12    return results;
13}

Limitations

1. Only works for Mersenne numbers
2. Requires significant computational resources for large exponents
3. Memory intensive for very large numbers
4. Not suitable for general primality testing

Best Practices

When implementing the Lucas-Lehmer test:

1. Use appropriate data types (BigInt for JavaScript)
2. Implement efficient modular arithmetic
3. Consider memory management for large numbers
4. Verify input is appropriate (p should be prime)
5. Handle edge cases properly

For general primality testing, other algorithms like Miller-Rabin are more appropriate. The Lucas-Lehmer test should be used specifically for testing Mersenne numbers.