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)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
Printed from the PrimePages <> © Reginald McLean.