Primality testing for word-size integers

Every primality test in ulong_extras that answers yes or no is deterministic: for word-size integers, probable primality and primality coincide because the relevant pseudoprimes have been enumerated. The default function n_is_prime chooses its method by the size of $n$.

The method by size#

All trial division uses the multiplication trick of Divisibility testing by multiplication, so it involves no division instructions. For $n < 2^{32}$ the 32 divisibility tests have no branches and are vectorised by the compiler.

AlgorithmStrong probable prime testThe Miller–Rabin test for a single base. Every odd prime passes it, at most a quarter of the bases let a composite pass, and with tabulated pseudoprimes it becomes a proof of primality for word-size integers.

Choosing the second base#

For $n > 2^{32}$ that pass the base-2 test, n_is_prime computes a 15-bit hash of $n$ and reads a base $a < 2^{16}$ from a table of 32768 entries (64 KiB). The table was built from the Feitsma–Galway list of base-2 strong pseudoprimes [FeiGal2013] so that, in each hash bucket, the stored base exposes every pseudoprime in that bucket. This follows the approach of Forišek and Jančina [ForJan2015], whose table is eight times larger.

One family of pseudoprimes makes this hard: semiprimes $n = pq$ with $q = k(p - 1) + 1$ for $k \in \{2, \ldots, 9, 12\}$, for which reliable witnesses are rare. These are detected before the second test. Writing $p = x + 1$ gives $n = (x + 1)(kx + 1)$, so for each $k$ the candidate $x = \lfloor \sqrt{n/k} \rfloor$ is computed from a single floating-point square root and checked. This costs about a twentieth of a Fermat test.

The correctness of the whole procedure up to $2^{64}$ can be verified with the program examples/check_n_is_prime, which runs n_is_prime on every entry of the Feitsma–Galway table.

Other tests#

The other tests in the module are kept for comparison, for other applications, or as certificates:

• n_is_probabprime_BPSW (Baillie–PSW [PSW1980; BaiWag1980]) has no known counterexample at any size;
• n_is_prime_pocklington [Poc1914; BLS1975] and n_is_prime_pseudosquare [LukPatWil1996] produce proofs that do not depend on tables;
• n_ll_is_prime handles two-word integers, deterministically below about $2^{81}$, with the double-word exponentiations n_ll_small_2_powmod and n_ll_small_powmod_triple reduced with the two-word Barrett inverse $\lfloor B^3/n \rfloor$ computed by n_ll_small_preinv.

@misc{flint-doc-algorithms-number-theory-primality-word,
  author       = {{The FLINT team}},
  title        = {{Primality testing for word-size integers}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/algorithms/number-theory/primality-word.html},
  note         = {Generated 2026-11-02}
}