View Single Post
Old 2005-04-06, 13:19   #8
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

22·5·373 Posts
Thumbs up

Originally Posted by Vijay
Thank you for a warm welcome everyone!
I'm sure with our raising computer power, the next M prime is not to far before
it is uncovered
Not quite.

Although a proof is lacking, there are heuristical arguments to suggest
that the number of Mersenne primes between 2^n and 2^(2n) should
be (asymptotically) exp(gamma), where gamma is the Euler-Mascheroni
constant. i.e. there should be a little more than one Mersenne prime
in the exponent range from n to 2n, independent of n [on AVERAGE]

Each Mersenne prime test on M_p = 2^p-1 requires p multiplications mod
M_p. Each multiplication takes time O(p log p loglog p) via a weighted
discrete Fourier Transform. Thus, each test requires O(p^2 log p loglog p)
work. Given a newly discovered Mersenne prime M_p, the *expected*
work to then find the next one is

O( integral from p to 2p of x^2 log x loglog x dx)

For sufficiently large x we have:

O(x^2 log x loglog x) ~ x^(2+o(1))

Thus, the above integral can be approximated by:

int from p to 2p of x^(2 + o(1)) dx and this is at least 8 times the
work to find the previous Mersenne prime.

This project has been very lucky in its last two successes. We should expect
that every new Mersenne prime we find will be "roughly" an order of magnitude harder than the previous one.
R.D. Silverman is offline   Reply With Quote