Miller's Primality Test

If a number fails this test, it is not a Prime. If the number passes, it may be a Prime. A number passing Miller's test is called a Strong Pseudoprime to base $a$. If a number $n$ does not pass the test, then it is called a Witness for the Compositeness of $n$. If $n$ is an Odd, Positive Composite Number, then $n$ passes Miller's test for at most $(n-1)/4$ bases with $1\leq a\leq -1$ (Long 1995). There is no analog of Carmichael Numbers for Strong Pseudoprimes.

The only Composite Number less than $2.5\times 10^{13}$ which does not have 2, 3, 5, or 7 as a Witness is 3215031751. Miller showed that any composite $n$ has a Witness less than $70(\ln n)^2$ if the Riemann Hypothesis is true.

See also Adleman-Pomerance-Rumely Primality Test, Strong Pseudoprime

References

Long, C. T. Th. 4.21 in Elementary Introduction to Number Theory, 3rd ed. Prospect Heights, IL: Waveland Press, 1995.