FLINT3.7.0-dev
/
Algorithm

Strong probable prime test

Cost
One modular exponentiation with an exponent below n, about \log_2 n modular squarings.

The strong probable prime test, also called the Miller–Rabin test, checks with one modular exponentiation a condition that every odd prime satisfies. It goes back to Miller [Mil1976], who showed that it proves primality under the generalised Riemann hypothesis when enough bases are tried, and Rabin [Rab1980], who turned it into a randomised test.

Definition#

Definition 1. Let n > 2 be odd and write n - 1 = 2^s d with d odd. Then n is a strong probable prime to base a, or an a-SPRP, if

a^d \equiv 1 \pmod n \quad\text{or}\quad a^{2^r d} \equiv -1 \pmod n \text{ for some } 0 \le r < s.

A composite a-SPRP is a strong pseudoprime to base a.

Theorem 2. If n is an odd prime and n \nmid a, then n is an a-SPRP.

Proof. Let x_r = a^{2^r d} \bmod n for 0 \le r \le s, so that x_{r+1} = x_r^2. By Fermat's little theorem x_s = a^{n-1} \bmod n = 1. Let r be the least index with x_r = 1. If r = 0 we are done. Otherwise x_{r-1}^2 = 1 and x_{r-1} \ne 1. Since \mathbb{Z}/n\mathbb{Z} is a field, the only square roots of 1 are \pm 1, so x_{r-1} = n - 1.

The proof shows what the test detects: a composite n is exposed when the sequence x_0, x_1, \ldots reaches 1 through a square root of 1 other than \pm 1, or never reaches 1 at all.

Theorem 3 (Monier, Rabin). If n > 9 is odd and composite, then n is a strong pseudoprime to at most \varphi(n)/4 bases 1 \le a < n.

See [Mon1980; Rab1980] for the original proofs and [CraPom2005] for an exposition. Hence k random bases detect a composite with probability at least 1 - 4^{-k}, but FLINT never relies on this bound for word-size integers.

The test#

Algorithm 1: Strong probable prime test

Input: odd n > 2, a base 1 < a < n - 1, and the odd part d of n - 1.

Output: whether n is an a-SPRP.

  1. y \gets a^d \bmod n.
  2. If y = 1 or y = n - 1, return true.
  3. Repeat s - 1 times: set y \gets y^2 \bmod n; if y = n - 1, return true; if y = 1, return false.
  4. Return false.

Returning false early when y = 1 in step 3 is valid because 1 is then reached through a square root of 1 other than \pm 1.

Making it deterministic#

A single base is not a proof, but strong pseudoprimes are rare enough to be listed completely in a range. Feitsma and Galway [FeiGal2013] computed all 31894014 strong pseudoprimes to base 2 below 2^{64}. FLINT uses this in two ways.

  • Below 2^{32}, there are only 2314 base-2 strong pseudoprimes. After a base-2 test, n_is_prime looks n up in a hash table of them.
  • Above 2^{32}, a second base is chosen from a table indexed by a hash of n, in the spirit of Forišek and Jančina [ForJan2015]. Each table entry was chosen so that it is a witness for every base-2 pseudoprime that hashes to its slot. See Primality testing for word-size integers for the details.

The function n_ll_is_prime uses a different known result: for n below about 3.3 \cdot 10^{24}, testing the first 13 primes as bases is a proof [SorWeb2016].

Arithmetic#

The test is one modular exponentiation followed by up to s - 1 squarings, so its speed is that of modular multiplication. n_is_strong_probabprime2_preinv uses Möller–Granlund reduction and n_is_strong_probabprime_precomp floating-point reduction. Inside n_is_prime, the tests for n \ge 2^{32} run entirely in Montgomery form, which avoids the normalisation shifts and lets the comparisons with \pm 1 be done on Montgomery representatives directly.

int n_is_strong_probabprime2_preinv(ulong n, ulong ninv, ulong a, ulong d)
int n_is_strong_probabprime_precomp(ulong n, double npre, ulong a, ulong d)

Referenced from#

References#

  • [Mil1976] G. L. Miller, "Riemann's hypothesis and tests for primality", Journal of Computer and System Sciences 13 (1976), 300–317
  • [Rab1980] M. O. Rabin, "Probabilistic algorithm for testing primality", Journal of Number Theory 12 (1980), 128–138
  • [Mon1980] L. Monier, "Evaluation and comparison of two efficient probabilistic primality testing algorithms", Theoretical Computer Science 12 (1980), 97–108
  • [CraPom2005] R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, second edition, Springer (2005).
  • [FeiGal2013] J. Feitsma and W. Galway, "Tables of pseudoprimes and related data", http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html
  • [ForJan2015] M. Forisek and J. Jancina, "Fast Primality Testing for Integers That Fit into a Machine Word", SOFSEM 2015, https://ceur-ws.org/Vol-1326/020-Forisek.pdf
  • [SorWeb2016] Sorenson, Jonathan and Webster, Jonathan : Strong pseudoprimes to twelve prime bases. Math. Comp. 86 (2017), 985-1003, https://doi.org/10.1090/mcom/3134
Cite this page

The FLINT team, “Strong probable prime test,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/number-theory/strong-probable-prime.html (generated 2026-10-20).