Primality Tests

Naive

Given an integer $n$, we can check numbers up to $\sqrt{n}$ to find if a number divides $n$. If there is such a number, $n$ is composite. If not, $n$ is a prime. This gives the solution in $O(\sqrt{n})$.

Miller Rabin Test (deterministic ver.)

Now we know how to generate prime numbers fast. How about primality testing?

Naive solutions first. Given an integer $n$, we can check numbers up to $\sqrt{n}$ to find if a number divides $n$. If there is such a number, $n$ is composite. If not, $n$ is a prime. This gives the solution in $O(\sqrt{n})$.

Here's a "solution" in $O(c\ln n)$ using the fast exponentiation we will talk about in the next section. It's called Miller-Rabin Primality Test. I'll introduce the deterministic version. We probably (hopefully) won't see stuff like $n>4\cdot 10^9$ in contests.

Here's the sketch of the algorithm. Choose some set of $a$. We will run the algorithm with different $a$s, and the more $a$s we run this algorithm with, the more accurate this primality test is going to be.

Decompose $n-1$ as $2^s\cdot d$. Then check if the following holds. $a^d\not\equiv 1(\mathrm{mod}n)\text{ and }{a}^{2^{r}d}\not\equiv -1(\mathrm{mod}n)\text{ for all }r\in [0,s-1]$If there is an $a$ that satisfies this, $n$ is composite. If not, $n$ is a prime.

List for sufficient checks (deterministic)

• $n<4.7\cdot 10^9$ ➝ $a=2,7,61$
• $n<2^{64}$ ➝ $a=2,3,5,7,11,13,17,19,23,29,31,37$