TOPICS
Search

Miller's Primality Test


If a number fails Miller's primality test for some base a, 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 a. If a number n does not pass the test, then it is called a witness for the compositeness. If n is an odd, positive composite number, then n passes Miller's test for at most (n-1)/4 bases with -1<=a<=1 (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 n has a witness less than 70(lnn)^2 if the Riemann hypothesis is true.


See also

Adleman-Pomerance-Rumely Primality Test, Composite Number Problem, Strong Pseudoprime

Explore with Wolfram|Alpha

References

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

Referenced on Wolfram|Alpha

Miller's Primality Test

Cite this as:

Weisstein, Eric W. "Miller's Primality Test." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MillersPrimalityTest.html

Subject classifications