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 for primality. If we find a natural number greater than $1$ that is a divisor of $n$ , then $n$ is not 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;
}

Eratosthenes Sieve

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

Fermat primality test

Fermat’s little theorem

If $a$ is an integer and $p$ is a prime number where $0 < a < p$ , then $a^{p} \equiv a (\mod p)$

or alternatively

$a^{p - 1} \equiv 1 (\mod p)$

Proofs of this theorem can be found here

Some examples

3^{5 - 1} \equiv 81 \equiv 1 (\mod 5) 3^{11 - 1} \equiv 59049 \equiv 1 (\mod 11)

The converse of this theorem is not always true

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

an example:

5^{561 - 1} \equiv 1 (\mod 561) but 561 = 3 \cdot 11 \cdot 17

but:

3^{561 - 1} \equiv 375 (\mod 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} o t \equiv 1 (\mod 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}, \dots, a_{i}$ Fermat’s little theorem holds true, even though 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 and $p$ is a prime number where $0 < a < p$ and $p > 2$ , then $a^{f r a c p - 1 2} e q u i v \pm 1 (\mod p)$

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

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

which means that

a^{2 q} - 1 \equiv 0 (\mod p)

this can be factored as

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

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

Expressing Euler’s Primality Test formally:

If $a^{(n - 1) / 2} o t \equiv \pm 1 (\mod n)$ , where $g c d (a, n) = 1$ , then $n$ must be a composite number for one of the following reasons:

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

This test also has some false positives e.g.

3^{(341 - 1) / 2} \equiv 1 (\mod 341) 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}, \dots, 2^{i} where 0 \leq i \leq s

We know from Euler’s Primality Test that if $a^{n - 1} \equiv 1 (\mod n)$ then $a^{(n - 1) / 2} \equiv \pm 1 (\mod n)$ . Let’s say that $a^{(n - 1) / 2} \equiv 1 (\mod n)$ ; then, also because of Euler’s Primality Test, $a^{(n - 1) / 2^{2}} \equiv \pm 1 (\mod n)$ . What this says is that as long as we can take the square root of some $a^{(n - 1) / 2^{i}} \equiv 1 (\mod 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^{\frac{n - 1}{2^{i}}} (\mod n)$ , i.e., when $\frac{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} a r \equiv \pm 1 (\mod n)$ then it means that it’s the square root of $a^{2 q} \equiv 1 (\mod n)$ (obviously, $2 q \leq n - 1$ because $n - 1$ is even and must be divisible by at least $2$ ).

If $a^{q} o t \equiv \pm 1 (\mod n)$ , we have to analyze $a^{2} q (\mod n)$ and there are three possible outcomes:

$a^{2} q \equiv 1 (\mod n)$ , which by Euler’s Primality Test implies that $a^{q} \equiv \pm 1 (\mod n)$ , which contradicts the statement above; therefore, $n$ is composite
$a^{2} q \equiv - 1 (\mod n)$ , which by Euler’s Primality Test implies that it’s the square root of some $a^{2^{i} q}$ (where $0 < i < s - 1$ ), and which will eventually become $a^{n - 1} \equiv 1 (\mod n)$ by successive squaring; therefore, we can say that $n$ is a probable prime
$a^{2} q ≢ \pm 1 (\mod 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;
}

Naive test

Eratosthenes Sieve

Fermat primality test

Fermat’s little theorem

Euler primality test

Miller-Rabin primality test

Eratosthenes Sieve

Integer Factorization

Divisor Function