> > 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...
The theorem tells us, that since the SPRP test is polynomial in log n, and
the expected number of tests required is also polynomial, then, if GRH is
true, we have a deterministic primality test in polynomial time. At the
moment, the best verifiable polynomial-time tests are merely "probable
prime". For an arbitrary number "probable prime" is "pretty good", but proof
is elusive. I'll define "pretty good" in a moment.
> 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?
The initial test in MAPLE was quite weak (in relative terms) and was a
probable primality test, perhaps only PRP. After it was used quite
excessively, its weakness was found - and the function would return "prime"
for a large class of composites. Generally "probable prime" is pretty
tough - an n-digit probable prime is composite with probability around
10^(-n/10), due to research by Pomerance et al. Their results are somewhere
on Chris Caldwell's wonderful site. While this probability is minute beyond
human comprehension - less likely than hardware/software/programmer/user
error! - it isn't proof, because a larger class of composites are "probable
prime" to the test. For instance, all Mersennes of prime exponent are 2-PRP.
The test is now tougher. If MAPLE now identifies a probable prime, it tests
again, to another base, and if that also passes, it performs a test using a
Lucas sequence. Again these are probable prime tests, so it is possible (and
likely) composites exist that pass all three. I think Carl Pomerance himself
has offered a cash prize for anyone who could find a counterexample to the
"twice SPRP, one Lucas sequence" test - an indication that it is not an easy
task of mere computation.
> 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...
Is "probable prime" enough? Practically, perhaps yes. Mathematically,
obviously not!
Chris Nash
Lexington KY
UNITED STATES
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
