Miller-Rabin Primality Test: Probabilistic Prime Testing Explained with Examples

The Miller-Rabin Primality Test is a widely used probabilistic algorithm designed to efficiently determine if a large number is prime. Unlike deterministic tests, Miller-Rabin leverages randomness to provide a high-confidence result in less time, making it popular in cryptography and computational number theory.

This detailed article will guide you through the concepts of primality testing, the mathematics behind Miller-Rabin, step-by-step examples with clear visual outputs, and interactive Python implementations that help deepen understanding.

Primality testing answers a fundamental question in number theory and computer science: Is a given integer n prime?

A prime number is a natural number greater than 1 that has no divisors other than 1 and itself. For small numbers, primality can be verified by trial division, but this becomes impractical as numbers grow large.

Efficient primality tests are essential in applications like cryptography (e.g., RSA), where large primes underpin security.

• Deterministic tests guarantee a correct answer but often have high computational complexity for very large numbers.
• Probabilistic tests like the Miller-Rabin test rely on randomness, providing a “probably prime” or “composite” result, with an extremely low probability of error for the prime case.

The Miller-Rabin test is one of the most practical probabilistic algorithms due to its balance of speed and reliability.

The test is based on properties derived from Fermat’s Little Theorem and modular exponentiation.

For an odd integer n > 2, the test expresses n – 1 as:

n - 1 = 2^r * d, where d is odd

We then choose a random base a such that 2 ≤ a ≤ n – 2 and check the following conditions:

• If a^d mod n = 1, then n could be prime (test passed for this a).
• Or for some i in [0, r-1], if a^(2^i * d) mod n = n - 1, then n could be prime.

If none of these hold, n is composite.

1. Express n-1 as 2^r * d, where d is odd.
2. Randomly select a base a with 2 ≤ a ≤ n-2.
3. Compute x = a^d mod n.
4. If x == 1 or x == n-1, proceed to next iteration (test passed for this base).
5. Repeat r-1 times: compute x = x^2 mod n.
6. If x == n-1 during any iteration, test passed for this base.
7. If none of these conditions meet, n is composite.
8. Repeat the test for multiple rounds to reduce error probability.

Step 1: Express 36 as \(36 = 2^2 \times 9\), so \(r = 2\) and \(d = 9\).

Step 2: Choose a base, say \(a = 2\).

Step 3: Compute \(x = 2^9 \mod 37\):

2^9 = 512; 512 mod 37 = 512 - (37*13) = 512 - 481 = 31

Step 4: Check \(x == 1\) or \(x == 36\)? No, \(x=31\).

Step 5: Square \(x\) modulo 37:

x = 31^2 mod 37 = 961 mod 37 = 961 - (37*25) = 961 - 925 = 36

Step 6: \(x = 36\) which is \(n-1\), so test passes for base \(a=2\).

This suggests 37 is likely prime. Repeating for other bases improves confidence.

The Miller-Rabin test is probabilistic because it uses random bases a. If the number passes the test for multiple bases, it is “probably prime” with a very small error chance.

The probability of a composite number passing the test as prime decreases exponentially with each additional round of testing using independent bases.

def miller_rabin_test(d, n, a):
    x = pow(a, d, n)
    if x == 1 or x == n - 1:
        return True
    while d != n - 1:
        x = (x * x) % n
        d *= 2
        if x == 1:
            return False
        if x == n - 1:
            return True
    return False

def is_prime_miller_rabin(n, k=5):
    if n <= 1 or n == 4:
        return False
    if n <= 3:
        return True
    d = n - 1
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1
    for _ in range(k):
        a = random.randint(2, n - 2)
        if not miller_rabin_test(d, n, a):
            return False
    return True

# Examples:
print(is_prime_miller_rabin(37))  # True
print(is_prime_miller_rabin(561)) # False (Carmichael number)

Run these examples interactively to check primality with very high confidence.

The Miller-Rabin Primality Test is a powerful probabilistic approach to prime checking, combining mathematical insight with computational efficiency. While it cannot guarantee primality with absolute certainty in one run, multiple rounds reduce error rates to negligible levels.

This makes Miller-Rabin particularly suitable for cryptographic applications and large number primality testing, where speed and reasonable assurance are key.