Motivation§

The existence of Carmichael numbers makes it difficult to create a primality testing algorithm based on Fermat tests.

The Miller-Rabin Algorithm§

The Miller-Rabin algorithm is a non-deterministic test for compositeness; i.e. if Miller-Rabin fails on a number $n$ then we say that $n$ is a probable prime. While non-deterministic, the probablity of failure is given by $4^{-k}$ where $k$ is the number of rounds of Miller-Rabin done, which means the failure probablity approaches zero very quickly.

There are Carmichael numbers that are strongly pseudoprime to a multitude of bases, but the occurrence of such numbers are extremely rare.

Theorem 16.1

Let $p$ be an odd prime and let $r = p - 1$. Let $k, q$ be values that satisfy $r = 2^k \cdot q$, and let $a$ be any integer not divisible by $p$.

Then, one of the following conditions are true

  • $a^q \equiv_p 1$.
  • One of $a^q, a^{2q}, a^{4q}, \dots, a^{2^{k-1}q}$ is congruent to $-1$ modulo $p$.

We know that $a^{p-1} \equiv 1 \pmod{p}$ by Fermat’s. Hence, $a^{2^{k-1}q} \equiv \pm 1$. If this value is $1$, then $a^{2^{k-2}q}$ is also and so on. If $a^{2^lq} \equiv_p 1$ holds for all non-negative $l$ strictly less than $k$, then the first statement holds. Otherwise, there must exist an $l$ such that the second statement holds.

Miller-Rabin Test

Suppose we want to factor an odd composite integer $n$.

  1. Find $k, q$ with $q$ odd such that $p - 1 = 2^k \cdot q$.
  2. Choose a random integer $a$.
  3. Compute $a^q \pmod{p}$. If $a^{q} \equiv_p \pm 1$, stop. The test fails, $n$ is a probable prime to $a$.
  4. Let $a^q \rightarrowtail a^{2q} \pmod{p}$.
    • If the value is $1$, stop. $a$ is a witness to the compositeness of $n$.
    • If the value is $-1$, stop. $n$ is a probable prime to base $a$.
  5. Repeat step 4 until $a^{2^{k-q}q}$.
  6. If the test has not terminated by this point, then $p$ is composite.