Miller's test

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)², 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)

• Fermat, Probable-Primality and Pseudoprimes
• Probable primes--how probable?

References:

Bach85

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