Which project finds bigger primes faster?

[Scarblac]

I've been wondering if we have a chance to ever find the biggest prime at that moment. Will GIMPS or some other project always be in front?

Assume equal computing power for a moment (we're not there yet I suppose, but who knows). Our numbers are of the form k2^n+1; we sieve a lot too. GIMPS are in front and search primes of the form 2^n-1, in terms of digits that's basically the same, I'm assuming they sieve as much as we do, at least.

We also search for several factors k at the same time.

As far as I remember (all this theory is vague in my head), Mersenne primes are easier to prove than Proth primes.

If we're lucky, there won't be another Mersenne prime for a long time, so we could pass them and find a bigger prime than they have, by pure luck.

Other than being lucky, we don't have much chance of passing them, right? How much more computing power would we need, relative to GIMPS?

Are there other projects who might find bigger primes even faster? Am I forgetting anything that influences this?

[MathGuy]

I think that the big difference between GIMPS and SB is the exponent range that we're working on. SB is currently only dealing with exponents up to 3M (although the sieving is in the works to extend this significantly) whereas GIMPS is essentially done with exponents below 10M and is testing up to 80M. They've got a BIG headstart, and, remember, GIMPS only needs to test prime exponents (not all exponents).

Having said that, though, the expected density of Mersenne primes is such that one would only expect to find 4 more primes in the current GIMPS search region of 80M. SB, on the other hand, expects to find 12 primes (although our search region will almost certainly need to be extended to do this).

So, one would expect that GIMPS will find *bigger* primes, while SB finds *more* primes.

[smh]

Numbers of the form 2^N-1 are easier to prove prime then numbers we are testing (actually we do a probable primality test while GIMPS does a true prime test). I think a Lucas Lehmer test is about 2 times faster on numbers of the same size, due to the half FFT size.

GIMPS indeed only needs to test prime exponents, and numbers of the form 2^N-1 have some special properties which makes it easy to factor them deep (over 2^60 for not to high exponents).
SoB otoh is testing numbers which have a low 'weight'. That is, a lot of numbers are elliminated by sieving. I think Phil Moore, in the sieving thread, calculated that we have to test less numbers per K in a given range.

Another type of numbers which are 'easy' to test are Generalised Fermat Numbers. (numbers of the form K^(2^N)+1). I think they test in about the same time as a mersenne exponent of the same size. Take a look in the larges know primes list. 17 of the 27 largest known primes are GFN's (6 are Mersenne and 4 are proth numbers (2 from SoB))

[nuutti]

Here are some empirical results from density :
Mersennes
n : 20,400,000 -> 25,350,000
number of not factored numbers : 126,374

This information is from :
http://www.mersenne.org/status.htm

SB or bust, multiplier 67607
n : 20,400,000 -> 25,350,000
149,041 n's remaining when factored up to p=93,216,281
Factoring a lot higher should decerease this number.

So may be when we have only one number remaining in our range
it will be more sparse than mersennes.

Yours,

Nuutti