A prime number is a natural number greater than $1$ which has no positive divisors other than $1$ and itself

## Naive test

Let $n$ be the number we want to check if is prime, if we find a natural number greater than $1$ that is a divisor of $n$ then $n$ is not a prime

• if a number $n$ is divisible by $k$ then $k \leq \sqrt{n}$

Complexity: $O(\sqrt{n})$

bool is_prime(int n) {
if (n == 2) {
// 2 is a prime number
return true;
}
if (n == 1 || (n % 2 == 0)) {
// 1 or any multiple of 2 is not a prime number
return false;
}
for (int i = 3; i * i <= n; i += 2) {
// check for any odd number < sqrt(n) if they are multiples of n
if (n % i == 0) {
return false;
}
}
return true;
}

## Erathostenes Sieve

If we have to make constants queries to check for numbers that are prime less than some number $n$ we can preprocess them using the Erathostenes Sieve and answer each query in $O(1)$

## Fermat primality test

### Fermat’s little theorem

If $a$ is an integer, $p$ a prime number where $0 < a < p$ then $$a^p \equiv a \pmod{p}$$

or alternatively

$$a^{p-1} \equiv 1 \pmod{p}$$

Proofs of this theorem can be found here

Some examples

$$3^{5 - 1} \equiv 81 \equiv 1 \pmod{5} \\ 3^{11 - 1} \equiv 59049 \equiv 1 \pmod{11}$$

The converse of this theorem is not always true

If $$a^{n - 1} \equiv 1 \pmod{n}$$ for some value of $0 < a < n$ then $n$ is prime

an example:

$$5^{561 - 1} \equiv 1 \pmod{561} \text{ but 561 = 3 \cdot 11 \cdot 17 }$$

but:

$$3^{561 - 1} \equiv 375 \pmod{561}$$

we can’t use the theorem directly to test if a number is prime since there’s a chance that the input is one of these special numbers (called Carmichael numbers) and the algorithm will give false positives e.g. $a = 5, p = 561$

what we can do is run the algorithm multiple times increasing the probability of finding a number $a$ such that $a^{p - 1} \not\equiv 1 \pmod{p}$ thus proving that $p$ is composite

// C++11
#include <random>

bool is_probably_prime(unsigned long long p, int iterations) {
if (p == 2) {
return true;
}
if (p % 2 == 0 || p == 1) {
return false;
}

std::random_device rd;
std::mt19937 engine(rd());
std::uniform_int_distribution<long long> dis(2, p - 2);
while (iterations--) {
// choose an integer between 2 and n-2
long long a = dis(engine);
if (binary_exponentiation_modulo_m(a, p - 1, p) != 1) {
return false;
}
}
return true;
}

No matter how many iterations we use in the algorithm above there’s a chance that for each $a_1, a_2, \ldots, a_i$ Fermat’s little theorem holds true even though that the input is composite therefore this test is not used in practice

## Euler primality test

Euler primality test is an improvement over the Fermat primality test because it adds another equality condition that a prime number must fulfill, assuming that $p$ is a prime number and $a$ is an integer where $0 < a < p$ then

If $a$ is an integer, $p$ a prime number where $0 < a < p$, $p > 2$ then $$a^{\tfrac{p - 1}{2}} \equiv \pm 1 \pmod{p}$$

The motivation to this definition comes to the fact that any prime $> 2$ is an odd number, then the prime number can be expressed as $2q + 1$ where $q$ is an integer thus

$$a^{(2q + 1) - 1} \equiv 1 \pmod{p}$$

which means that

$$a^{2q} - 1 \equiv 0 \pmod{p}$$

this can be factored as

$$(a^q - 1)(a^q + 1) \equiv 0 \pmod{p}$$

therefore $a^q$ is congruent to two possible values $1$ and $-1$. Going back to the definition of $q$, $2q + 1 = p$ we can find the value of $q$ as $q = \tfrac{(p - 1)}{2}$

Expressing Euler’s primality test formally:

If $a^{(n - 1) / 2} \not\equiv \pm 1 \pmod n$ where $gcd(a, n) = 1$ then $n$ must be a composite number for one of the following reasons:

• if $a^{n - 1} \not\equiv 1 \pmod{n}$ then $n$ must be composite by Fermat’s Little Theorem
• if $a^{n - 1} \equiv 1 \pmod{n}$ then $n$ must be composite because $a^{(n - 1) / 2}$ which is a square root of $a^{n - 1} \pmod{n}$ must fulfill the following equivalence $a^{(n - 1) / 2} \equiv \pm 1 \pmod n$ which is a condradiction to the statement above

This test also has some false positives e.g.

$$3^{(341 - 1)/2} \equiv 1 \pmod{341} \text{ but 341 = 11 * 31 }$$

## Miller-Rabin primality test

The Miller-Rabin primality test is quite similar to Euler’s primality test, but instead of looking at the square root of $a^{n - 1}$ it looks at the sequence of square roots/powers of two derived from $a^{n - 1}$

Let $2^s$ be the largest power of $2$ that divides $n - 1$, then $n - 1 = 2^s \cdot q$ for some odd integer $q$, the sequence of powers of two that divide $n - 1$ is

$$2^0, 2^1, \ldots, 2^i \quad \text{where 0 \leq i \leq s}$$

We know from Euler’s primality test that if $a^{n - 1} \equiv 1 \pmod{n}$ then $a^{(n - 1) / 2} \equiv \pm 1 \pmod{n}$, let’s say that $a^{(n - 1) / 2} \equiv 1 \pmod{n}$ then also because of Euler’s primality test $a^{(n - 1) / 2^2} \equiv \pm 1 \pmod{n}$, what this says is that as long as we can take the square root of some $a^{(n - 1) / 2^i} \equiv 1 \pmod{n}$ the result must be $\pm 1$ otherwise it’s a composite number by Euler’s primality test

The base case occurs when we cannot take the square root of some $a^{\tfrac{n - 1}{2^i}} \pmod{n}$ i.e. when $\tfrac{n - 1}{2^i}$ is no longer divisible by $2$ which is exactly the number $q$, for this base case we’re sure of something, if $a^q \equiv \pm 1 \pmod{n}$ then it means that it’s the square root of $a^{2q} \equiv 1 \pmod{n}$ (obviously $2q \leq n - 1$ because $n - 1$ is even and must be divisible by at least $2$)

If $a^q \not\equiv \pm 1 \pmod{n}$ we have to analyze $a^2q \pmod{n}$ and there’re three possible outcomes:

• $a^2q \equiv 1 \pmod{n}$ which by Euler’s primality test implies that $a^q \equiv \pm 1 \pmod{n}$ which contradicts the statement above, therefore $n$ is composite
• $a^2q \equiv -1 \pmod{n}$ which by Euler’s primality test implies that it’s the square root of some $a^{2^iq}$ (where $0 < i < s-1$), which will eventually become $a^{n - 1} \equiv 1 \pmod{n}$ by successive squaring, therefore we can say that $n$ is a probable prime
• $a^2q \not\equiv \pm 1 \pmod{n}$ which is the same as the statement above (therefore we have to keep analyzing the next element in the sequence)
// C++11
#include <random>

bool miller_rabin_primality_test(long long a, long long n) {
int s = 0;
long long q = n - 1;
while (q % 2 == 0) {
q /= 2;
s += 1;
}
long long m = binary_exponentiation_modulo_m(a, q, n);
if (m == 1 || m == n - 1) {
// base case a^q ≡ 1 (mod n)
return true;
}
for (int i = 0; i < s; i += 1) {
// a^{2^iq} (mod n)
m = (m * m) % n;
if (m == n - 1) {
return true;
}
}
return false;
}

bool is_probably_prime(long long p, int iterations) {
// NOTE: test of the primes 2 and 3 because of
// the distribution limits (p, p - 2)
if (p == 2 || p == 3) {
return true;
}
if (p % 2 == 0 || p == 1) {
return false;
}
std::random_device rd;
std::mt19937 engine(rd());
std::uniform_int_distribution<long long> dis(2, p - 2);
while (iterations--) {
// choose an integer between 2 and n-2
long long a = dis(engine);
if (!miller_rabin_primality_test(a, p)) {
return false;
}
}
return true;
}