Miller's test
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000:
GIMPS has discovered a new largest known prime number: 282589933-1 (24,862,048 digits)

Should the generalized Riemann hypothesis be proved, the following would gives us a powerful test for primality.

Millers Test: Assume the generalized Riemann hypothesis is true. If n is an a-SPRP for all integers a with 1 < a < 2(log n)2, then n is prime.
The constant 2 (which will no doubt be improved) is due to Bach.

See Also: Pseudoprime, PRP

Related pages (outside of this work)


E. Bach, Analytic methods in the analysis and design of number-theoretic algorithms, A.C.M. Distinguished Dissertations The MIT Press, Cambridge, MA, 1985.  pp. xiii+48, ISBN 0-262-02219-2. MR 87i:11185

Chris K. Caldwell © 1999-2019 (all rights reserved)