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