M43: GIMPS project has found a new Mersenne prime

T.Rex

Hi,

The GIMPS project has found a new Mersenne prime: M43 !

[tex]\large 2^{30,402,457} - 1[/tex]

It is the 43th known Mersenne prime and it is the new largest known prime.

It has 9,152,052 digits ! So the BIG ONE (more than 10 millions digits) is still to be found ! (and its discoverer will get about $50,000).

Its primality has been checked 2 times: first by myself in 4 days and 21 hours using a 16x Itanium2 1.5 GHz Bull NovaScale computer, then by Jeff Gilchrist with Alpha and then Itanium2 1.6 GHz computers. Both with the Glucas program of Guillermo Ballester Valor.

The story is fully described at GIMPS and Press Release.
If you read French, there is a translation: GIMPS and Communiqué de Presse.

It is the second Mersenne prime found by the GIMPS project in 2005.
And we hope to find a new one before end of 2006 !

Happy New Year !

Tony

-Job-

Wow, easy money huh? :P

Nereid

Now if only I'd not deleted GIMPS in favour of Einstein@Home on my PC ....

This is awesome (and congrats to you T.Rex for your role).

Perhaps you'd be kind enough to say a few words about the other distributed searches that the GIMPS folk offer those willing to devote some spare PC cycles to?

T.Rex

I'm not sure I understand perfectly the question ...
If you ask about the other searches that you can do with the mprime program delivered by the GIMPS, you also can contribute to search factors of Mersenne composites or of Fermat composites, or of any number of the form: 2^n+/-1 (Cunningham project).
Tony

Nereid

Yep, that's just what I was asking Tony

Would anyone like to say a few words about what these other searches aim to find (and why they have some connection with searching for Mersenne primes)?

shmoe

gimps uses what's called pollard's P-1 method to look for small factors before it does the Lucas-lehmer test. This will find a factor P when P-1 is smooth, meaning all the prime factors of P-1 are less than some given bound. This works well on numbers of the form 2^n-1 and Fermat numbers 2^(2^n)+1, both of which have prime divisors that like Pollard's method, i.e. the prime divisors of a fermat number are of the form k*2^(n+2)+1, on it's way to being smooth. I'd expect optimizing the code for these types of numbers would be similar. I believe gimps also uses elliptic curve factoring as well.

Fermat numbers are prime for n=0 to 4, and known composite up to n=32 or somewhere in that neighbourhood (and probably some higher ones as well). It's expected that there are only finitely many Fermat primes, possibly only the known 5. They get huge fast so I don't think too much work is done on trying to prove fermat numbers to be prime, rather you just hope that factors will pop up.

the cunningham project is looking for factors of numbers b^n+1 and b^n-1, obvious generalizations of mersenne and fermat numbers. This dates back some 80 years ago. The most compelling reasons to do this are probably to keep a benchmark of current computational and algorithmic capabalities and a sense of completeness of filling in holes in the tables.

T.Rex

My guess is that someone will try to study the primality of F33 (the first Fermat number which status (prime or not) is unknown) in the next 6 years. With a fast current PC, the search would take around 4000 years ! But, in 5 years, I guess that hundred-cores processors, hundred-chips computers and fast parallelized programs will be available ! So that it should take less than 1 year.
Since primality (or not) of Fermat Numbers can be done by means of the LLT (the algorithm inside the GIMPS mprime program and inside GLucas), the basic code is available. Just wait for more powerful computers !
Tony

shmoe

LLT usually refers to the Mersenne specific Lucas-Lehmer test, no? How does it apply to fermat numbers? Or does gimps include code for pepin's test as well (I'd expect the coding would be similar)? Do you know how much parallelization can speed these up? Seems like the only place for this kind of improvement is the FFT used for the squaring.

MathematicalPhysicist

it raises a good question, which is: what two tests for primality have you used?
i know of just one, which is fermat test for primality of a number.
so what algorithm have you used, if it's not a secret from your behalf.

cheers, man or female. (-:

T.Rex

The LLT, with different details, applies to different kinds of numbers. As an example, I've wrote papers proving that it can be used for Fermat numbers: 2 theorems for Fermat numbers, and LLT for Fermat. This was known long time ago (and forgotten). So, the GIMPS prime95 program could also run the LLT for Fermat numbers, with very small modifications (S_0=5 and modulo). But, since next Fermat number with unknown status is F33, it would take 4000 years with a fast PC to know if it is prime or not ... So I think George has no plan to extend prime95 this way !
About parallelization, Glucas verified M43 approximately 7 times faster than prime95 on 1 PC and by using 16 CPUs at 75%. But, if George could parallelize prime95, I guess he could get a better scalability, since Glucas is in C and prime95 in assembler.
LLT can also be used for numbers of the form: k*2^n +/- 1 : it is the LLR Lucas Lehmer Riesel test.
Tony

T.Rex

Both GIMPS prime95 and Guillermo Valor Glucas programs use the Lucas-Lehmer-Test (LLT), based on Lucas sequences. This is a very simple test that can be used for some numbers (maybe more but I'm not aware of): Mersenne numbers, Fermat numbers, and k*2^n +/- 1 (LL-Riesel).
The LLT has been discovered by Edouard Lucas and proved rigouresly by Derrick Lehmer. See: Mersenne Wiki and Primality Tests
Tony

shmoe

I hadn't seen different versions lumped under the common name "LLT" before.

That doesn't make massive parallelization look too hopefull. Where does the speed up occur? The FFT?

With dual core machines looming over the home pc market, do you know if gimps is planning to head in this direction? Given the already pretty short times to test for mersenne primes, it doesn't seem like it would be worth it for the bulk of the testing, you won't get 2x speed, so you may as well run two instances on different numbers, there's plenty to go around. No such abundance of attackable Fermat numbers though!

T.Rex

Look at this link. Follow links at bottom.
I have not clear scalability numbers: I've not run prime95 and Glucas on the same multi-CPUs i386 machine yet.
Glucas speeds up the LLT because the FFT has been parallelized: it uses several threads. Best performance appears with 1 thread per CPU. I really don't know how Mr Valor did this parallelization ...
It seems future processors will have more cores and will run slower. Also the exponents currently tested by the GIMPS take more than 1 month of computation on a fast machine used 7/7 24/24. So, people with a fast PC but using it only 4 hours a day can check only 2 exponents a year ! So the risk of loosing all the data due to a disk or Windows failure becomes very important. In the next future, in order to enable GIMPS testers to see results every months, they should need to use double-core machines and parallelized prime95. Also, people want to see results in a human time-frame: 6 months is already too long. But I don't know if George Woltman has plans about parallelizing prime95 ... A huge work, probably. (Remember it is written in assembler and must run both on Windows and on UNIX/Linux.
Tony

Mindscrape

Haha. That's ridiculous.

T.Rex

Would you mind elaborate ? What is ridiculous ?

Mindscrape

In a good way. Just how enormous the 43rd Mersenne prime is comes across as astonishing.