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 . If a number does not pass the test, then it
is called a Witness for the Compositeness of . 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 only Composite Number less than which does not have 2, 3, 5, or 7 as a Witness is 3215031751. Miller showed that any composite has a Witness less than if the Riemann Hypothesis is true.

**References**

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

© 1996-9

1999-05-26