Nathan Russell observes:
> Well, unless there is an announcement within the next few hours, 2000
> will be the first calender year in the history of GIMPS without a
> Mersenne prime.
>
> Is the number of searchers, and the power of their hardware, increasing
> enough to keep up with the increased runtimes and (slightly) decreased
> chance of a given exponent being prime? Or can we expect only one prime
> every several years, as was the case before the start of the GIMPS
> effort?
The chance that a given Mp is prime is O(1/log(Mp)) = O(1/p).
The LL test for Mp needs O(p) iterations.
The time per iteration (using an FFT) is about O(p*log(p)).
So the estimated time per LL test is O(p^2 * log(p))
whereas the chance of success on one LL test is O(1/p).
We need a few adjustments to the formula since (for example)
the time to trial divide by primes < N is approximately
O(log(p) /p) for fixed N. [We test O(N/p) divisors below N,
with a cost of O(log(p)) per divisor.] This trial division
time decreases with p, whereas LL time increases, which
affects our strategy.
Nonetheless, to test all O(2^b / b) primes with b bits,
we estimate O(2^b / b) * O(2^(2b) * b) = O(8^b) operations
with O(1) expected successes. Doing all 24-bit p's
takes about eight times as long as doing all 23-bit p's.
Even with more contributors and faster hardware,
we soon get diminishing returns.
Peter Montgomery
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
