4. Miller Rabin Algorithm

In encryption algorithms, say RSA, finding large primes are usually the first step. How to find a relatively large prime becomes one crucial problem to solve. Another relevant problem is to check whether a given number is a prime or composite number. Miller Rabin Algorithm is a primality test algorithm.

4.1. Algorithm

The task is to test whether number \(n\) is prime or not.

  • Find numbers \(s\) and \(d\) such that \(2^s \cdot d = n-1\).

Because if n looks like a prime, it should not be even (unless it’s 2), or a multiply of 5.

  • Select a random integer \(a < n-1\) and check if \(a^d ~mod~n = 1\). If so, \(n\) maybe prime. Change \(a\) and repeat this algorithm.

  • For \(j = 0, 1, 2, \cdots, s-1\), check if \(a^{2^j d} ~mod~n = -1\). If so, \(n\) maybe prime. Change \(a\) and repeat this algorithm. If the answer keeps to be false, \(n\) is a composite number.

4.2. Explanation

According to Fermat’s little theorem, if \(n\) is prime, \(a^{p-1}~mod~p = 1\) for all integer \(a\) . If \(n\) is not prime, we can always find an \(a\) such that \(a^{n-1} \neq 1~mod~n\).

If \(a^d \neq 1~mod~n\) but \(n = 1+2^s d\) is a prime number, then the sequence

\[a^d~mod~n, a^{2d}~mod~n, a^{4d}~mod~n, \cdots, a^{2^s d}~mod~n\]

stops by 1. We can directly compute \(a^{n-1}~mod~n\), but if we can find another smaller exponent smaller than \(n-1\), we save times and computational power.

Suppose we find \(j\) such that \(a^{2^j d}~mod~n = 1\), then \((a^{2^j d})^{2^{s-j}}~mod~n = 1\).

4.3. Error Analysis

If the algorithm returns “composite”, \(n\) is definitely not prime. But if returns “maybe prime”, the number “n” has probability \(1/4\) to make an error. The integer \(a\) to cause an error is called “strong liar”. To make the “False Detection” error as low as possible, you can keeps changing \(a\).