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.

$y \gets a^d \bmod n$ .
If $y = 1$ or $y = n - 1$ , return true.
Repeat $s - 1$ times: set $y \gets y^2 \bmod n$ ; if $y = n - 1$ , return true; if $y = 1$ , return false.
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#

Primality proving: APRCL and ECPP (algorithm)
Primality testing for word-size integers (overview)
What FLINT guarantees (overview)
n_is_strong_probabprime2_preinv, n_is_strong_probabprime_precomp

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-11-02).

@misc{flint-doc-algorithms-number-theory-strong-probable-prime,
  author       = {{The FLINT team}},
  title        = {{Strong probable prime test}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/algorithms/number-theory/strong-probable-prime.html},
  note         = {Generated 2026-11-02}
}

Edit this page · PDF version · Built with fdoc from 0a4634bf95