Primality: Miller-Rabin

17 Dec 2021

Notes Cryptography Primality: Miller-Rabin

§ 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.

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$ .

Find $k, q$ with $q$ odd such that $p - 1 = 2^k \cdot q$ .
Choose a random integer $a$ .
Compute $a^q \pmod{p}$ . If $a^{q} \equiv_p \pm 1$ , stop. The test fails, $n$ is a probable prime to $a$ .
Let $a^q \rightarrowtail a^{2q} \pmod{p}$ $a^{q} ↣ a^{2 q} (mod 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$ .
Repeat step 4 until $a^{2^{k-q}q}$ .
If the test has not terminated by this point, then $p$ is composite.