Deterministic Primality Testing for Limited Bit Width

Problem: Determine if a 32-bit number is prime (deterministically)

Solution: (in C++)

// Bases to test. Using the first 4 prime bases makes the test deterministic
// for all 32-bit integers. See https://oeis.org/A014233.
int64_t bases[] = {2, 3, 5, 7};
inline int countTrailingZeros(uint64_t n) {
if (n == 0)
return 64;
return __builtin_ctzll(n);
}
int64_t modularExponentiation(int64_t base, int64_t exponent, int64_t modulus) {
int64_t res = 1;
int64_t b = base % modulus;
int64_t e = exponent;
while (e > 0) {
if (e & 1) {
// Doesn't overflow because we assume 32-bit integer inputs
res = (res * b) % modulus;
}
b = (b * b) % modulus;
e >>= 1;
}
return res;
}
bool isPrime(int64_t n) {
if (n < 2) return false;
if (n < 4) return true;
if (!(n & 1)) return false;
int64_t d = n - 1;
unsigned s = countTrailingZeros(d);
d = d >> s;
for (uint64_t a : bases) {
if (n <= a) break;
int64_t x = modularExponentiation(a, d, n);
if (x == 1 || x == n - 1)
continue;
bool composite = true;
for (unsigned r = 1; r < s; ++r) {
// Doesn't overflow because it is at most n < 32 bits
x = (x * x) % n;
if (x == n - 1) {
composite = false;
break;
}
}
if (composite)
return false;
}
return true;
}

Discussion: In the late 1980’s Gary Miller and Michael Rabin came up with their now-famous Miller-Rabin primality test. It provided a randomized algorithm to check if an integer is prime, which had a tunable parameter to increase the probability of being correct.

The intervening 40 years has seen a huge body of research improving both randomized and deterministic primality testing. In 2002, Agrawal, Kayal, and Saxena found a condition-free deterministic polynomial-time algorithm, and the Ballie-PSW test is still often used today.

A strong pseudoprime is a composite number that passes Miller-Rabin’s deterministic test for a particular prime base $a$. For example, if you only check Miller-Rabin with a base of 2, $2047 = 23 \cdot 89$ will pass the test. Testing 2, 3, and 5 means the smallest pseudoprime is 25,326,001. Adding 7 to this list provides a deterministic test for all 32-bit integers. For 64-bit integers, a set of 7 specific bases can be used to maintain determinism.