Primality Test

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 <= i <= 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;
}