Miller's Primality Test 

If a number fails Miller's primality test for some base , it is not a prime. If the number passes, it may be a prime. A composite number passing Miller's test is called a strong pseudoprime to base . If a number  does not pass the test, then it is called a witness for the compositeness. If  is an odd, positive composite number, then  passes Miller's test for at most  bases with  (Long 1995). There is no analog of Carmichael numbers for strong pseudoprimes.

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 showed that any composite  has a witness less than  if the Riemann hypothesis is true.

REFERENCES:

Caldwell, C. "Finding Primes & Proving Primality. 2.3: Strong Probable-Primality and a Practical Test." https://primes.utm.edu/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.

Sloane, N. J. A. Sequence A074773 in "The On-Line Encyclopedia of Integer Sequences."