"how numbers are stored and used in computers"

Baillie-PSW Primality Test

The Baillie-PSW test is a probabilistic primality test that combines the Miller-Rabin test with a Lucas probable prime test. Despite being probabilistic, no composite number has been found that passes the test, making it extremely reliable for practical purposes.

Mathematical Foundation

The Baillie-PSW test consists of three main steps:

Trial division by small primes
A Miller-Rabin primality test with base 2
A Lucas probable prime test with carefully chosen parameters

The test uses the following mathematical concepts:

For the Lucas test part, we use:

where and are the roots of the quadratic equation for carefully chosen and .

Time and Space Complexity

The time complexity is:

The space complexity is:

JavaScript Implementation

Here's a complete implementation of the Baillie-PSW 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 millerRabinBase2(n) {
19    if (n <= 1n || n === 4n) return false;
20    if (n <= 3n) return true;
21    
22    // Write n-1 as d * 2^s
23    let s = 0n;
24    let d = n - 1n;
25    while (d % 2n === 0n) {
26        s++;
27        d /= 2n;
28    }
29    
30    // Test with base 2
31    let x = modPow(2n, d, n);
32    if (x === 1n || x === n - 1n) return true;
33    
34    while (s > 1n) {
35        x = (x * x) % n;
36        if (x === n - 1n) return true;
37        if (x === 1n) return false;
38        s--;
39    }
40    
41    return false;
42}
43
44function findLucasParameters(n) {
45    let d = 5n;
46    let sign = 1n;
47    
48    while (true) {
49        const jacobiSymbol = calculateJacobiSymbol(d * sign, n);
50        if (jacobiSymbol === -1n) {
51            return [1n, d * sign];
52        }
53        
54        d += 2n;
55        sign = -sign;
56        
57        if (d > 1000n) {
58            throw new Error("Suitable parameters not found");
59        }
60    }
61}
62
63function calculateJacobiSymbol(a, n) {
64    if (n <= 0n || n % 2n === 0n) {
65        throw new Error("n must be positive odd number");
66    }
67    
68    a = a % n;
69    let result = 1n;
70    
71    while (a !== 0n) {
72        while (a % 2n === 0n) {
73            a = a / 2n;
74            const mod8 = n % 8n;
75            if (mod8 === 3n || mod8 === 5n) {
76                result = -result;
77            }
78        }
79        
80        [a, n] = [n, a];
81        if (a % 4n === 3n && n % 4n === 3n) {
82            result = -result;
83        }
84        a = a % n;
85    }
86    
87    return n === 1n ? result : 0n;
88}
89
90function lucasTest(n) {
91    if (n === 2n) return true;
92    if (n <= 1n || n % 2n === 0n) return false;
93    
94    const [p, d] = findLucasParameters(n);
95    const q = 1n;
96    
97    // Calculate n+1 = d * 2^s
98    let s = 0n;
99    let k = n + 1n;
100    while (k % 2n === 0n) {
101        s++;
102        k /= 2n;
103    }
104    
105    // Calculate initial Lucas sequence values
106    let u = 1n;
107    let v = p;
108    let q2 = 2n * q;
109    k = k / 2n;
110    
111    // Main loop
112    while (k > 0n) {
113        if (k % 2n === 1n) {
114            u = (u * v) % n;
115            v = (v * v - q2) % n;
116        }
117        v = (v * v - q2) % n;
118        k = k / 2n;
119    }
120    
121    if (u === 0n) return true;
122    
123    // Additional checks
124    for (let r = 0n; r < s; r++) {
125        v = (v * v - q2) % n;
126        if (v === 0n) return true;
127    }
128    
129    return false;
130}
131
132function bailliePSW(n) {
133    // Convert to BigInt
134    n = BigInt(n);
135    
136    // Step 1: Trial division by small primes
137    const smallPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37];
138    for (let p of smallPrimes) {
139        if (n === BigInt(p)) return true;
140        if (n % BigInt(p) === 0n) return false;
141    }
142    
143    // Step 2: Miller-Rabin base 2
144    if (!millerRabinBase2(n)) return false;
145    
146    // Step 3: Lucas test
147    return lucasTest(n);
148}
149
150// Example usage:
151console.log(bailliePSW(17));    // true
152console.log(bailliePSW(561));   // false (Carmichael number)

Optimized Implementation

Here's a version optimized for numbers below 2⁶⁴:

code.js
1function optimizedBailliePSW(n) {
2    if (n <= 1 || n === 4) return false;
3    if (n <= 3) return true;
4    
5    // Quick check for small factors
6    if (n % 2 === 0) return false;
7    
8    // Use lookup table for small primes
9    const smallPrimes = new Set([
10        3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
11    ]);
12    
13    if (smallPrimes.has(n)) return true;
14    if ([...smallPrimes].some(p => n % p === 0)) return false;
15    
16    // Perform strong base-2 pseudoprime test
17    if (!millerRabinBase2(BigInt(n))) return false;
18    
19    // Perform Lucas test
20    return lucasTest(BigInt(n));
21}

Applications

The Baillie-PSW test is used in:

Computer algebra systems (e.g., Mathematica)
Cryptographic applications
Number theory research
Prime number generation

Best Practices

When implementing Baillie-PSW:

Use appropriate data types (BigInt for large numbers)
Implement efficient modular arithmetic
Handle edge cases properly
Consider using optimized versions for smaller numbers
Combine with other tests for critical applications

Limitations

Probabilistic nature (though no counterexamples known)
Slower than simpler tests like Miller-Rabin
Complex implementation
Requires careful parameter selection

Performance Considerations

To optimize performance:

Use trial division for small numbers
Implement efficient modular arithmetic
Use lookup tables for small primes
Consider parallel processing for multiple tests

Historical Significance

The Baillie-PSW test is significant because:

No composite number has been found that passes it
Combines deterministic and probabilistic approaches
More reliable than single-algorithm tests
Widely used in mathematical software

For most practical applications, the Baillie-PSW test provides an excellent balance of reliability and performance.