Miller-Rabin Test

The Miller-Rabin test is a probabilistic algorithm used to determine whether a number is prime.

It is particularly useful for very large numbers, where deterministic methods become impractical due to their computational complexity.

As a probabilistic primality test, it does not always provide a definitive answer. Instead, it classifies numbers as either prime or "probably prime."

How It Works
Practical Example
Final Thoughts

How It Works

The test is based on Fermat's Little Theorem: If $ p $ is a prime number, then for any integer $ a $ such that $ 1 \leq a < p $, the following holds:

$$ a^{p-1} \equiv 1 \pmod{p} $$

However, this condition alone is not sufficient, as some composite numbers (called Fermat pseudoprimes) also satisfy the equation.

The Miller-Rabin test improves upon this by factoring $ p-1 $ and checking additional modular conditions.

To test an odd integer $ n > 3 $:

Express $ n-1 $ in the form $ 2^s \cdot d $, where $ d $ is odd. This is done by repeatedly dividing $ n-1 $ by 2.
Example: If $ n = 25 $, then $ n-1 = 24 = 2^3 \cdot 3 $. Here, $ s=3 $ and $ d=3 $.
Randomly pick a base $ a $ in the range $ 2 \leq a \leq n-2 $.
Example: If $ n = 25 $, the base $ a $ must be chosen from $ 2 \leq a \leq 23 $.
Compute $ x = a^d \mod n $.
Example: If $ n = 25 $, $ a=2 $, $ s=3 $, and $ d=3 $, then: $$ x = 2^3 \mod 25 $$
If $ x \equiv 1 \pmod{n} $ or $ x \equiv n-1 \pmod{n} $, then $ n $ passes the test and is likely prime. The process stops here.

Otherwise, proceed to the next step.
Example: In this case, $ x = 2^3 \mod 25 = 8 $ does not immediately confirm primality, but this alone is not enough to declare $ n $ composite. So, we continue testing with $ x=8 $.
Square $ x $ modulo $ n $ and check:
- If $ x \equiv n-1 \pmod{n} $, the test is passed, and $ n $ is likely prime.
- If $ x \equiv 1 $, then $ n $ is definitely composite.
Repeat this process up to $ s-1 $ times. If none of these iterations confirm primality, then $ n $ is composite.
Example: Continuing from the previous step, $ x = 8^2 \mod 25 = 14 $ is inconclusive, so we iterate again with $ x = 14 $.

False Positives and Probability of Error

For each base $ a $, the probability of mistakenly identifying a composite number as prime (a false positive) is at most $ 1/4 $. However, by testing multiple bases, this probability decreases exponentially.

To minimize the risk of error, it is recommended to repeat the test $ k $ times with different bases $ a $.

If the test is performed $ k $ times with randomly chosen bases, the probability of incorrectly classifying a composite number as prime is at most $ \frac{1}{4^k} $.

If the number fails the test in any round, it is definitely composite.
If it passes all rounds for a given number of bases, it is considered "probably prime."

For example, if $ n < 2^{64} $, it has been proven that checking all bases up to $ \min(n-1, \lfloor 2\sqrt{\log(n)} \rfloor) $ guarantees a deterministic primality test.

The algorithm has a time complexity of $ O(k \cdot \log^3 n) $, where $ k $ is the number of bases tested.

Practical Example

Let's determine whether $ n = 25 $ is a prime number.

$$ n = 25 $$

We express $ n-1 = 24 $ in the form $ 2^s \cdot d $:

$$ n-1 = 24 = 2^3 \cdot 3 $$

So, we have $ s = 3 $ and $ d = 3 $.

Next, we compute $ x = a^d \mod n $, selecting a random base $ a $ from the range $ 2 \leq a \leq n-2 $. Let's choose $ a = 2 $.

$$ x = a^d \mod n $$

$$ x = 2^3 \mod 25 $$

$$ x = 8 \mod 25 $$

The result is $ x = 8 $ since $ 8 \div 25 = 0 $ with a remainder of $ 8 $.

$$ x = 8 $$

Since $ x \neq 1 $ and $ x \neq n-1 = 24 $, we continue with the next step.

Now, we compute $ x = x^2 \mod n $ for $ s-1 = 3-1 = 2 $ iterations.

$$ x = 8^2 \mod 25 $$

$$ x = 64 \mod 25 $$

The result is $ x = 14 $ since $ 64 \div 25 = 2 $ with a remainder of $ 14 $.

$$ x = 14 $$

Since $ x \neq 24 $, we proceed to the next iteration.

We compute $ x = x^2 \mod n $ again using the previous result $ x = 14 $.

$$ x = 14^2 \mod 25 $$

$$ x = 196 \mod 25 $$

The result is $ x = 21 $ since $ 196 \div 25 = 7 $ with a remainder of $ 21 $.

$$ x = 21 $$

Since $ x \neq 24 $ and we have reached the second iteration ($ s-1 = 2 $), we conclude that $ 25 $ is not a prime number; it is composite.

Example 2

Now, let's check if $ n = 11 $ is prime.

We express $ n-1 = 10 $ as $ 2^s \cdot d $.

Dividing 10 by 2 gives 5, which is no longer divisible by 2.

$$ n-1 = 10 = 2^1 \cdot 5 $$

So, $ s = 1 $ and $ d = 5 $.

We compute $ x = a^d \mod n $, choosing $ a = 2 $:

$$ x = 2^5 \mod 11 $$

$$ x = 32 \mod 11 $$

$$ x = 10 $$

Since $ x = n-1 = 10 $, the test suggests that $ 11 $ is likely prime.

To increase confidence, we repeat the test with another base, $ a = 3 $.

$$ x = 3^5 \mod 11 $$

$$ x = 243 \mod 11 $$

$$ x = 1 $$

Since $ x = 1 $, the test is also passed with $ a = 3 $, reinforcing that $ 11 $ is prime.

Note: Running the test twice ($ k = 2 $) with bases $ a = 2 $ and $ a = 3 $ both confirmed the same result. The probability of a false positive is now very low, at most $ \frac{1}{4^k} = \frac{1}{4^2} = \frac{1}{16} = 0.0625 $, or 6.25%.

Example 3

Let's check if $ n = 29 $ is prime.

We express $ n-1 = 28 $ as $ 2^s \cdot d $.

Dividing 28 by 2 gives 14, and dividing 14 by 2 gives 7, which is no longer divisible by 2.

$$ n-1 = 28 = 2^2 \cdot 7 $$

So, $ s = 2 $ and $ d = 7 $.

We compute $ x = a^d \mod n $, choosing $ a = 2 $:

$$ x = 2^7 \mod 29 $$

$$ x = 128 \mod 29 $$

$$ x = 12 $$

Since $ x = 12 $, we continue with another iteration ($ s-1 = 1 $).

$$ x = 12^2 \mod 29 $$

$$ x = 144 \mod 29 $$

$$ x = 28 $$

Since $ x = n-1 = 28 $, the test is passed for $ a = 2 $, suggesting that $ 29 $ is prime.

However, the probability of a false positive remains high at $ \frac{1}{4} = 25\% $.

To further reduce this probability, we repeat the test with another base, $ a = 3 $.

$$ x = 3^7 \mod 29 $$

$$ x = 2187 \mod 29 $$

$$ x = 12 $$

Since $ x = 12 $ is inconclusive, we perform another iteration.

$$ x = 12^2 \mod 29 $$

$$ x = 144 \mod 29 $$

$$ x = 28 $$

Since $ x = n-1 = 28 $, the test is also passed for $ a = 3 $, further confirming that $ 29 $ is prime.

With two rounds of testing, the false positive probability drops to $ \frac{1}{4^2} = 6.25\% $.

Running additional tests with more bases can reduce it even further.

Final Thoughts

In summary, the Miller-Rabin test is a fast, efficient, and widely used method for determining the primality of large numbers.

It plays a crucial role in cryptographic algorithms like RSA, where identifying prime numbers is essential.

Although probabilistic, running a sufficient number of iterations makes it highly reliable in practice.