FAQ author Lucas Wiman <[EMAIL PROTECTED]> writes
> Well, this might not be a problem. If P-1 tries more than one base,
> all that is required (per Mn) is *one* gcd. We just multiply the
> remainders from the bases mod Mn, and then take the gcd on the final
> remainders. We could have the program prompt the user for the time when
> the computer is on but not being used when they ask for a P-1 assignment.
> Or, we could have it run so that the program stops functioning when the
> computer is being used. It could just save the intermediate files to
> disk, to free up memory for the user who (graciously) gives us their
> CPU cycles.
>
You might rerun P-1 with larger limits, but don't bother rerunning
using a new base. If q is a prime factor of Mp, and r is the largest
prime factor of q-1, then a fraction 1 - 1/r of all possible bases
will require us to include exponent r in step 1 or step 2 of P-1.
If r > 100000, this is 99.999% of all potential bases.
The base change can be useful if P-1 finds a composite GCD.
For example 2717 = 11*13*19. If we start with base b = 7,
using exponents 4 and 3, then
b^4 = 2401 == -316 (mod 2717)
(b^4)^3 == -31554496 == 742 (mod 2717)
Here GCD(b^12 - 1, 2717) = 247 is composite (13*19).
This is because 13-1 divides the exponent 4*3 and because
our choice b = 7 is a cube (also a square) mod 19,
with (19-1)/3 dividing 4*3. Choosing a b which is not
a cube modulo 19 lets P-1 factor 247.
Peter Montgomery
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
