Hi folks
><< There are actually no counterexample for p<1500, I've checked them all.
>>
>Interesting. Is this actually as nasty (computationally) as a LL test?
Because
>the exponentiation is to Mp/2...
Computationally its equally as tough - the exponentiation is done by
repeated squarings (so (Mp-1)/2 = M(p-1) is not as good as it looks), and
the iteration count (plus calculation complexity) is effectively identical.
It is possible that if the test fails proving compositeness the residue
could assist in factoring (but the same could probably be said of a LL test
residue with a little more work).
I quickly tested p<15593, no counterexamples. Quite an arbitrary place to
stop, but the chance of a larger counterexample is minute, to say the least.
Some figures by Pomerance et al suggest that if a random n-digit number is
strong pseudoprime to some random base, then it is composite with
probability less than 10^-(n/10) or thereabouts - sum that over all
Mersennes of prime exponent >=15593, and the expected number of
counterexamples is minute - it's less than a GP, first term 2^-1559.3,
common ratio 1/4. (assuming of course that the base 3 is 'random' enough in
relation to Mersenne numbers. The brave may wish to write 3=2+1 and use the
binomial theorem).
Ballpark estimate - the odds of a counterexample are about 10^500 to 1. The
result is "probably true", as much as any "strong probable prime" result is
probably true.
Chris Nash
Lexington KY
UNITED STATES
=======================================================
Co-discoverer of the 7th and 10th largest known primes.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
