The smallest numbers that are strong pseudoprimes to base 2, 3, 5, and 7 (and would hence fail a test based on these bases) are 3215031751, 118670087467, 307768373641,
315962312077, ... (OEIS A074773; Jaeschke 1993).
Miller (1976) showed that any composite has a witness
less than
if the generalized Riemann hypothesis
is true. Rabin's randomized version chooses bases independently and uniformly (Rabin
1980). Since at most one quarter of the admissible bases are strong liars for any
odd composite, independent rounds have error probability
at most .
This randomized algorithm is commonly called the Miller-Rabin primality test.
Caldwell, C. "Finding Primes & Proving Primality. 2.3: Strong Probable-Primality and a Practical Test." https://t5k.org/prove/prove2_3.html.Jaeschke,
G. "On Strong Pseudoprimes to Several Bases." Math. Comput.61,
915-926, 1993.Long, C. T. Th. 4.21 in Elementary
Introduction to Number Theory, 3rd ed. Prospect Heights, IL: Waveland Press,
1995.Miller, G. "Riemann's Hypothesis and Tests for Primality."
J. Comput. System Sci.13, 300-317, 1976.Rabin, M. O.
"Probabilistic Algorithm for Testing Primality." J. Number Th.12,
128-138, 1980. https://doi.org/10.1016/0022-314X(80)90084-0.Sloane,
N. J. A. Sequence A074773 in "The
On-Line Encyclopedia of Integer Sequences."
. Write 
, where 
is odd. The test checks a base
with 
.
The base passes if 
or 
for some 
. Otherwise, 
is a witness to the compositeness
of 
.
A composite number that passes is called a strong pseudoprime to base 
. There is no analog of Carmichael
numbers for strong pseudoprimes.
has a witness
less than 
if the generalized Riemann hypothesis
is true. Rabin's randomized version chooses bases independently and uniformly (Rabin
1980). Since at most one quarter of the admissible bases are strong liars for any
odd composite 
, 
independent rounds have error probability
at most 
.
This randomized algorithm is commonly called the Miller-Rabin primality test.
