On Sun, 16 May 1999, Chris Jefferson wrote:
> Sorry, just a quick question!
> In various places, I have read that the generalized Riemann hypothesis is
> true, then there is a very simple test for primeness, namely if n is an
> a-SPRP for all integers a<2(log n)^2, then n is prime. From a computation
> viewpoint, is this actually of any use, as it will show if numbers are
> composite and if it is quick, then primes could be checked using it, then
> double checked via another means, also giving the opportunity to disprove
> a major hypothesis of maths...
Just adding a reference and a related question...
This test is known as Miller's test.
You can read about it in Caldwell's excellent home page about prime
numbers: http://www.utm.edu/research/primes/
The exact location of the reference to Miller's test there is
http://www.utm.edu/research/primes/prove/prove2.html#sprp
Most mathematical programs/packages (maple, gmp, ...)
which are capable of dealing with large integers
have a "probably_prime" function.
The documentation usually does not explain exactly what the algorithm is.
I could be wrong, but I think these are a-SPRP tests,
possibly Miller's test itself. Does anyone know for sure?
As to the idea of using it to try to disprove grh,
the best thing would be for cryptography programs which routinely
generate relatively big "probably prime" numbers to use Miller's test
and keep an eye on possible failures. It would probably be hard to
convince people to introduce that feature, though...
http://www.mat.puc-rio.br/~nicolau
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
