Primality tests

One way to prove that a given number $m$ is prime is to find one of its primitive roots.

Choose a random $a$ between $2$ and $m-2$.

If $gcd(a.m) \ne 1$, then $m$ is not prime. Better yet, the greatest common divisor allows us to partially factor $m$.

By Fermat's little theorem, we know that $a^{m-1} \equiv 1 mod m$. If this is not so, then definitely $m$ is not prime.

Furthermore, when $m$ is an odd number, we must have either $a^{(m-1)/2} \equiv 1 mod m$ or $a^{(m-1)/2} \equiv -1modm$.

Now, it can be shown that $a$ is a primitive root modulo $m$ if, for every prime divisor $d$ of $m-1$, we have $a^{(m-1)/d} mod m \ne 1$. If $a$ satisfies these conditions then the order of $a$ modulo $m$ must be $m-1$, and thus $m$ must be prime.

If not, try another $a$.

These exist composite numbers, called Carmichael numbers, for which $a^{m-1}mod m = 1$ for all $a$ which are relatively prime to $m$. For these numbes, $\lambda(m) \mid (m-1)$.

The Miller-Rabin primality test

Goal: to test if the odd number $n$, with $n \gt 3$, is a prime number or not.

Result of the test: either $n$ is not prime or it may be prime (a probable primer number); in the second case, the probability that the test fails to identify a composite number is at most 0.25.

How it is done (to increase confidence on the result, do steps 2 to 6 several times):

1. Let $n-1$ be written as $n-1 = 2^rd$, with $d$ an odd number (so $r$ is as large as possible).

2. Select at random an integer $a$ uniformly distributed in the interval $2\le a \le n-2$.

3. If $gcd(a,n) \ne 1$, then $n$ is definitely a composite number.

4. Compute $x_0 = a^d mod n$. If $x_0 = 1$ or $x_0 = n -1$ then $n$ is a probale prime.

5. Otherwise, for $k = 1, 2, ..., d-1$, compute $x_k = x²_{k-1} mod n$. If $x_k = n - 1$ then $n$ is a probable prime.

6. Finally, if we get here, say that $n$ is definitely a composite number (because Fermat's little theorem failed because $a^{(m-1)/2} \equiv \pm 1 modm$).

The composite numbers that pass this test (meaning that the algorithm above says that they are probable primes) for a given $a$ are called base-$a$ strong pseudo-primes.