Deterministic Primality Testing for Limited Bit Width

Summary

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. See Wikipedia and my 2013 Program Gallery entry. It was notable in that 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, designed around the same time as Miller-Rabin, is still often used today in conjunction with Miller-Rabin. One of my favorite papers showing the importance of doing primality testing properly is in cryptography, Albrecht et al’s 2018 paper...