Paul Derbyshire writes:
I notice that GIMPS exponents are tested with a bit of trial
factoring and then we go straight to LL testing, without any
pseudoprime testing. I assume that pseudoprime tests are actually
slower than the LL test itself? Or else they'd use them to
eliminate some composite numbers before going on to the LL tests...
The pseudo-prime test requires effectively the same amount of CPU
time, since the only real difference is that the LL test does the
subtraction of two each iteration. The real issue is that the
pseudo-prime test is not certain, since some composites "look" prime
to it. The LL test is certain, barring errors during execution.
(I am aware that Mersenne numbers are always strong
2-pseudoprimes. I was thinking along the lines of other bases.)
Base 3, e.g., which is where mers3p.c of the mers package came from,
due to a prior discussion of this on this mailing list. Compare it to
the recently posted LL test program implemented on top of GMP.
Will
http://www.garlic.com/~wedgingt/mersenne.html
`
