tags | |
---|---|
|
This article describes multiple algorithms to determine if a number is prime or not.
By definition a prime number doesn't have any divisors other than
We try to find a non-trivial divisor, by checking if any of the numbers between
bool isPrime(int x) {
for (int d = 2; d * d <= x; d++) {
if (x % d == 0)
return false;
}
return x >= 2;
}
This is the simplest form of a prime check. You can optimize this function quite a bit, for instance by only checking all odd numbers in the loop, since the only even prime number is 2. Multiple such optimizations are described in the article about integer factorization.
This is a probabilistic test.
Fermat's little theorem (see also Euler's totient function) states, that for a prime number
In general this theorem doesn't hold for composite numbers.
This can be used to create a primality test.
We pick an integer
However it is also possible, that the equation holds for a composite number.
So if the equation holds, we don't have a proof for primality.
We only can say that
By running the test for all possible bases
bool probablyPrimeFermat(int n, int iter=5) {
if (n < 4)
return n == 2 || n == 3;
for (int i = 0; i < iter; i++) {
int a = 2 + rand() % (n - 3);
if (binpower(a, n - 1, n) != 1)
return false;
}
return true;
}
We use Binary Exponentiation to efficiently compute the power
There is one bad news though:
there exist some composite numbers where
The Fermat test is still being used in practice, as it is very fast and Carmichael numbers are very rare.
E.g. there only exist 646 such numbers below
The Miller-Rabin test extends the ideas from the Fermat test.
For an odd number
This allows us to factorize the equation of Fermat's little theorem:
If
holds or
holds for some
If we found a base
Similar to the Fermat test, it is also possible that the set of equations is satisfied for a composite number.
In that case the base
Here is an implementation for 64 bit integer.
using u64 = uint64_t;
using u128 = __uint128_t;
u64 binpower(u64 base, u64 e, u64 mod) {
u64 result = 1;
base %= mod;
while (e) {
if (e & 1)
result = (u128)result * base % mod;
base = (u128)base * base % mod;
e >>= 1;
}
return result;
}
bool check_composite(u64 n, u64 a, u64 d, int s) {
u64 x = binpower(a, d, n);
if (x == 1 || x == n - 1)
return false;
for (int r = 1; r < s; r++) {
x = (u128)x * x % n;
if (x == n - 1)
return false;
}
return true;
};
bool MillerRabin(u64 n, int iter=5) { // returns true if n is probably prime, else returns false.
if (n < 4)
return n == 2 || n == 3;
int s = 0;
u64 d = n - 1;
while ((d & 1) == 0) {
d >>= 1;
s++;
}
for (int i = 0; i < iter; i++) {
int a = 2 + rand() % (n - 3);
if (check_composite(n, a, d, s))
return false;
}
return true;
}
Before the Miller-Rabin test you can test additionally if one of the first few prime numbers is a divisor.
This can speed up the test by a lot, since most composite numbers have very small prime divisors.
E.g.
Miller showed that it is possible to make the algorithm deterministic by only checking all bases
This is still a pretty large number of bases.
So people have invested quite a lot of computation power into finding lower bounds.
It turns out, for testing a 32 bit integer it is only necessary to check the first 4 prime bases: 2, 3, 5 and 7.
The smallest composite number that fails this test is
This results in the following deterministic implementation:
bool MillerRabin(u64 n) { // returns true if n is prime, else returns false.
if (n < 2)
return false;
int r = 0;
u64 d = n - 1;
while ((d & 1) == 0) {
d >>= 1;
r++;
}
for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
if (n == a)
return true;
if (check_composite(n, a, d, r))
return false;
}
return true;
}
It's also possible to do the check with only 7 bases: 2, 325, 9375, 28178, 450775, 9780504 and 1795265022. However, since these numbers (except 2) are not prime, you need to check additionally if the number you are checking is equal to any prime divisor of those bases: 2, 3, 5, 13, 19, 73, 193, 407521, 299210837.