Miller-Rabin Primality Test

The Miller-Rabin primality test is a sophisticated probabilistic primality testing algorithm that provides strong guarantees of correctness. It's widely used in cryptographic applications due to its efficiency and reliability.

Mathematical Foundation

The Miller-Rabin test is based on two key mathematical properties:

1. For any prime , we can write , where is odd and .

2. For any prime and any base coprime to , either:

   • , or
   • There exists where such that

If neither condition holds for a given base , then is definitely composite. If either condition holds, is probably prime.

Time and Space Complexity

For rounds of testing, the time complexity is , and the space complexity is .

Implementation

code.js
1function modPow(base, exponent, modulus) {
2    if (modulus === 1) return 0;
3    
4    let result = 1n;
5    base = BigInt(base) % BigInt(modulus);
6    exponent = BigInt(exponent);
7    modulus = BigInt(modulus);
8    
9    while (exponent > 0n) {
10        if (exponent % 2n === 1n) {
11            result = (result * base) % modulus;
12        }
13        base = (base * base) % modulus;
14        exponent = exponent / 2n;
15    }
16    
17    return result;
18}
19
20function millerRabinTest(n, k = 20) {
21    // Handle small numbers
22    if (n <= 1 || n === 4) return false;
23    if (n <= 3) return true;
24    
25    // Convert to BigInt for large number handling
26    n = BigInt(n);
27    
28    // Write n-1 as d * 2^s
29    let s = 0n;
30    let d = n - 1n;
31    while (d % 2n === 0n) {
32        s++;
33        d /= 2n;
34    }
35    
36    // Witness function
37    function witness(a) {
38        // Compute a^d % n
39        let x = modPow(a, d, n);
40        if (x === 1n || x === n - 1n) return false;
41        
42        // Square x s-1 times
43        for (let r = 1n; r < s; r++) {
44            x = (x * x) % n;
45            if (x === n - 1n) return false;
46            if (x === 1n) return true;
47        }
48        
49        return true;
50    }
51    
52    // Use deterministic bases for n < 2⁶⁴
53    if (n < 2n ** 64n) {
54        const bases = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37];
55        for (let base of bases) {
56            if (n === BigInt(base)) return true;
57            if (witness(base)) return false;
58        }
59        return true;
60    }
61    
62    // For larger numbers, use random bases
63    for (let i = 0; i < k; i++) {
64        const a = 2n + BigInt(Math.floor(Math.random() * (Number(n) - 4))) + 1n;
65        if (witness(a)) return false;
66    }
67    
68    return true;
69}
70
71// Example usage:
72console.log(millerRabinTest(17));   // true
73console.log(millerRabinTest(561));  // false (Carmichael number)

Deterministic Version

For numbers below , we can make the Miller-Rabin test deterministic by using specific bases.

code.js
1function isPrime(n) {
2    if (n <= 1 || n === 4) return false;
3    if (n <= 3) return true;
4    
5    // Deterministic bases for different ranges
6    const bases = n < 1_373_653 ? [2, 3] :
7                 n < 9_080_191 ? [31, 73] :
8                 n < 4_759_123_141 ? [2, 7, 61] :
9                 n < 2_152_302_898_747 ? [2, 3, 5, 7, 11] :
10                 n < 3_474_749_660_383 ? [2, 3, 5, 7, 11, 13] :
11                 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37];
12    
13    // Write n-1 as d * 2^s
14    let s = 0;
15    let d = n - 1;
16    while (d % 2 === 0) {
17        s++;
18        d = Math.floor(d / 2);
19    }
20    
21    for (let a of bases) {
22        if (a >= n) break;
23        let x = modPow(a, d, n);
24        if (x === 1 || x === n - 1) continue;
25        
26        let composite = true;
27        for (let r = 1; r < s; r++) {
28            x = (x * x) % n;
29            if (x === n - 1) {
30                composite = false;
31                break;
32            }
33        }
34        if (composite) return false;
35    }
36    
37    return true;
38}

Applications

The Miller-Rabin test is used in many important applications:

1. Cryptographic key generation
2. SSL/TLS certificate generation
3. Digital signatures
4. Random prime number generation
5. Public key cryptography systems

Best Practices

When implementing Miller-Rabin:

1. Use BigInt for numbers larger than 2⁵³
2. Use deterministic version for numbers < 2⁶⁴
3. Choose appropriate number of rounds (k) based on security requirements
4. Combine with trial division for small factors
5. Use cryptographically secure random number generation

Performance Optimizations

1. Small Prime Testing: For small numbers, use trial division
2. Deterministic Bases: Use predetermined bases for numbers < 2⁶⁴
3. Parallel Testing: Test multiple bases concurrently
4. Precomputation: Cache commonly used values

code.js
1function optimizedPrimalityTest(n) {
2    // Quick check for small numbers
3    if (n <= 1 || n === 4) return false;
4    if (n <= 3) return true;
5    if (n % 2 === 0) return false;
6    
7    // Trial division for small factors
8    for (let i = 3; i <= 100 && i * i <= n; i += 2) {
9        if (n % i === 0) return false;
10    }
11    
12    // Use Miller-Rabin for larger numbers
13    return millerRabinTest(n);
14}

Limitations

1. Probabilistic nature (though with very high confidence)
2. Computational intensity for very large numbers
3. Need for good random number generation
4. Complex implementation compared to simpler tests

Despite these limitations, Miller-Rabin remains the preferred choice for most practical applications requiring prime testing.