----- Original Message -----
From: "Frank_A_L_I_N_Y" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Sunday, December 31, 2000 7:59 PM
Subject: Re: Mersenne: 2000 - first calender year without a Mersenne
> Sorry, I replied to Mr Russell before reading Mr Montgomery's reply.
> Mr M said it much better than I.
>
> Reagards Frank
> ----- Original Message -----
> From: <[EMAIL PROTECTED]>
> To: <[EMAIL PROTECTED]>
> Sent: Sunday, December 31, 2000 6:46 PM
> Subject: Re: Mersenne: 2000 - first calender year without a Mersenne
>
>
> >
> > 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
>
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
