A prime number is a natural number greater than
which has no positive divisors other than and itself
Naive test
Let
- if a number
is divisible by then
Complexity:
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
Fermat primality test
Fermat’s little theorem
If
is an integer, a prime number where then or alternatively
Proofs of this theorem can be found here
Some examples
The converse of this theorem is not always true
If
for some value of then is prime
an example:
but:
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.
what we can do is run the algorithm multiple times increasing the probability of finding a number
// 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
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
If
is an integer, a prime number where , then
The motivation to this definition comes to the fact that any prime
which means that
this can be factored as
therefore
Expressing Euler’s primality test formally:
If
- if
then must be composite by Fermat’s Little Theorem - if
then must be composite because which is a square root of must fulfill the following equivalence which is a condradiction to the statement above
This test also has some false positives e.g.
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
Let
We know from Euler’s primality test that if
The base case occurs when we cannot take the square root of some
If
which by Euler’s primality test implies that which contradicts the statement above, therefore is composite which by Euler’s primality test implies that it’s the square root of some (where ), which will eventually become by successive squaring, therefore we can say that is a probable prime 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;
}