Pocklington-Lehmer Primality Test

The Pocklington-Lehmer primality test is a deterministic primality test that can prove a number is prime by finding a partial factorization of n - 1. It's particularly useful when n - 1 has a large prime factor.

Mathematical Foundation

The test is based on the following theorem:

Let be an integer and suppose that where:

2. All prime factors of are known
3. For each prime factor of , there exists an integer such that:

Then is prime.

Time and Space Complexity

The time complexity depends on the factorization of , but the primality test itself is in , and the space complexity is .

JavaScript Implementation

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

code.js
1function modPow(base, exponent, modulus) {
2    if (modulus === 1n) return 0n;
3    
4    let result = 1n;
5    base = base % modulus;
6    
7    while (exponent > 0n) {
8        if (exponent % 2n === 1n) {
9            result = (result * base) % modulus;
10        }
11        base = (base * base) % modulus;
12        exponent = exponent / 2n;
13    }
14    
15    return result;
16}
17
18function gcd(a, b) {
19    a = BigInt(Math.abs(Number(a)));
20    b = BigInt(Math.abs(Number(b)));
21    
22    while (b) {
23        [a, b] = [b, a % b];
24    }
25    
26    return a;
27}
28
29function findPrimeFactors(n) {
30    const factors = [];
31    let num = n;
32    
33    // Handle factors of 2
34    while (num % 2n === 0n) {
35        factors.push(2n);
36        num = num / 2n;
37    }
38    
39    // Handle odd factors
40    for (let i = 3n; i * i <= num; i += 2n) {
41        while (num % i === 0n) {
42            factors.push(i);
43            num = num / i;
44        }
45    }
46    
47    // If num > 1, it's prime
48    if (num > 1n) {
49        factors.push(num);
50    }
51    
52    return [...new Set(factors)]; // Return unique factors
53}
54
55function pocklingtonLehmer(n) {
56    // Convert to BigInt and handle small cases
57    n = BigInt(n);
58    if (n <= 1n) return false;
59    if (n <= 3n) return true;
60    if (n % 2n === 0n) return false;
61    
62    const nMinus1 = n - 1n;
63    const sqrt = BigInt(Math.floor(Math.sqrt(Number(n))));
64    
65    // Find prime factors of n-1
66    const primeFactors = findPrimeFactors(nMinus1);
67    
68    // Try to find suitable F and R
69    for (let i = 0n; i < primeFactors.length; i++) {
70        const F = nMinus1 / primeFactors[i];
71        
72        if (F > sqrt - 1n) {
73            // Try different bases
74            for (let a = 2n; a < 20n; a++) {
75                const powerMod = modPow(a, nMinus1, n);
76                if (powerMod !== 1n) continue;
77                
78                const factor = modPow(a, F, n);
79                if (gcd(factor - 1n, n) === 1n) {
80                    return true;
81                }
82            }
83        }
84    }
85    
86    return false;
87}
88
89// Example usage:
90console.log(pocklingtonLehmer(17));  // true
91console.log(pocklingtonLehmer(561)); // false (Carmichael number)

Extended Implementation

Here's a more comprehensive version that includes additional checks:

code.js
1function extendedPocklingtonLehmer(n) {
2    // Handle small cases
3    if (n <= 1n) return false;
4    if (n <= 3n) return true;
5    if (n % 2n === 0n) return false;
6    
7    // Trial division by small primes
8    const smallPrimes = [3n, 5n, 7n, 11n, 13n, 17n, 19n, 23n, 29n, 31n];
9    for (const p of smallPrimes) {
10        if (n === p) return true;
11        if (n % p === 0n) return false;
12    }
13    
14    const nMinus1 = n - 1n;
15    const sqrt = BigInt(Math.floor(Math.sqrt(Number(n))));
16    
17    // Find complete factorization of n-1
18    const factors = findPrimeFactors(nMinus1);
19    
20    // Try different factorizations
21    for (let mask = 1; mask < (1 << factors.length); mask++) {
22        let F = 1n;
23        for (let i = 0; i < factors.length; i++) {
24            if (mask & (1 << i)) {
25                F *= factors[i];
26            }
27        }
28        
29        if (F > sqrt - 1n) {
30            // Try different bases
31            for (let a = 2n; a < 20n; a++) {
32                let isValid = true;
33                
34                // Check first condition
35                if (modPow(a, nMinus1, n) !== 1n) {
36                    continue;
37                }
38                
39                // Check second condition for each prime factor
40                for (const q of factors) {
41                    const power = nMinus1 / q;
42                    const value = modPow(a, power, n);
43                    if (gcd(value - 1n, n) !== 1n) {
44                        isValid = false;
45                        break;
46                    }
47                }
48                
49                if (isValid) return true;
50            }
51        }
52    }
53    
54    return false;
55}

Applications

The Pocklington-Lehmer test is useful in several contexts:

1. Proving primality when n-1 has a large prime factor
2. Generating certified prime numbers
3. Cryptographic applications
4. Number theory research

Best Practices

When implementing the test:

1. Use efficient modular arithmetic
2. Handle large numbers appropriately (BigInt)
3. Implement robust prime factorization
4. Consider combining with other tests
5. Use optimized GCD algorithms

Performance Optimizations

1. Efficient Modular Exponentiation:

code.js
1function optimizedModPow(base, exponent, modulus) {
2    if (modulus === 1n) return 0n;
3    
4    const bits = exponent.toString(2);
5    let result = 1n;
6    base = base % modulus;
7    
8    for (const bit of bits) {
9        result = (result * result) % modulus;
10        if (bit === '1') {
11            result = (result * base) % modulus;
12        }
13    }
14    
15    return result;
16}

2. Optimized GCD:

code.js
1function binaryGCD(a, b) {
2    if (b === 0n) return a;
3    
4    let shift = 0n;
5    while ((a | b) & 1n === 0n) {
6        a >>= 1n;
7        b >>= 1n;
8        shift++;
9    }
10    
11    while (a & 1n === 0n) a >>= 1n;
12    
13    while (b !== 0n) {
14        while (b & 1n === 0n) b >>= 1n;
15        if (a > b) [a, b] = [b, a];
16        b -= a;
17    }
18    
19    return a << shift;
20}

Limitations

1. Requires factorization of n-1
2. Not efficient for all numbers
3. Complex implementation
4. May be slow for certain number types

Historical Significance

The test is important because:

1. One of the first deterministic primality tests
2. Led to development of other primality tests
3. Still useful in certain cases
4. Historically significant in number theory

For practical applications, this test is often combined with other methods or used in specific cases where n-1 has a known factorization.