M43: GIMPS project has found a new Mersenne prime

In summary, the GIMPS project has recently discovered a new Mersenne prime with the help of the mprime program. This new prime, M43, is the 43rd known Mersenne prime and has 9,152,052 digits. Its discovery was confirmed by two different computers using the LLT algorithm. The search for the next Mersenne prime, which could potentially have over 10 million digits, is ongoing and the project hopes to find it by the end of 2006. Other distributed searches for factors of Mersenne and Fermat numbers are also being conducted by GIMPS.
  • #1
T.Rex
62
0
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 http://www.oxixares.com/glucas/" [Broken]program of Guillermo Ballester Valor.

The story is fully described at http://www.mersenne.org/" [Broken].
If you read French, there is a translation: http://www.mersenne.org/french_prime.htm" [Broken].

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
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
Wow, easy money huh? :P
 
  • #3
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?
 
  • #4
Nereid said:
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?
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
 
  • #5
Yep, that's just what I was asking Tony :smile:

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)?
 
  • #6
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.
 
  • #7
shmoe said:
They get huge fast so I don't think too much work is done on trying to prove fermat numbers to be prime ...
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
 
  • #8
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.
 
  • #9
T.Rex said:
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 http://www.oxixares.com/glucas/" [Broken]program of Guillermo Ballester Valor.

The story is fully described at http://www.mersenne.org/" [Broken].
If you read French, there is a translation: http://www.mersenne.org/french_prime.htm" [Broken].

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
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. (-:
 
Last edited by a moderator:
  • #10
shmoe said:
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.
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: http://tony.reix.free.fr/Mersenne/PrimalityTest1FermatNumbers.pdf" [Broken]. 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
 
Last edited by a moderator:
  • #11
loop quantum gravity said:
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.
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: http://http://www.mersennewiki.org/index.php/Lucas-Lehmer_Test" [Broken]
Tony
 
Last edited by a moderator:
  • #12
T.Rex said:
The LLT, with different details, applies to different kinds of numbers

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

T.Rex said:
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

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!
 
  • #13
shmoe said:
I hadn't seen different versions lumped under the common name "LLT" before.
Look at this http://www.mersenneforum.org/showthread.php?p=5769&mode=threaded". Follow links at bottom.
That doesn't make massive parallelization look too hopefull. Where does the speed up occur? The FFT?
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 ...
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!
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
 
Last edited by a moderator:
  • #14
Haha. That's ridiculous.
 
  • #15
Mindscrape said:
Haha. That's ridiculous.
Would you mind elaborate ? What is ridiculous ?
 
  • #16
T.Rex said:
Would you mind elaborate ? What is ridiculous ?
In a good way. Just how enormous the 43rd Mersenne prime is comes across as astonishing.
 

1. What is the M43: GIMPS project?

The M43: GIMPS (Great Internet Mersenne Prime Search) project is a collaborative effort by volunteer computer users to discover and verify new Mersenne primes, which are a type of prime number that can be written in the form 2^n - 1. The project has been running since 1996 and has discovered the largest known prime numbers to date.

2. What is a Mersenne prime?

A Mersenne prime is a prime number that can be written in the form 2^n - 1, where n is also a prime number. These numbers are named after the French mathematician Marin Mersenne, who studied them in the 17th century. They are rare and have been the subject of fascination and study for centuries.

3. How was the new Mersenne prime discovered?

The new Mersenne prime, M43, was discovered by the GIMPS project using distributed computing. This means that volunteers from around the world run a special software on their personal computers that tests different numbers for primality. Once a potential prime number is found, it is then verified by independent computers to ensure its accuracy.

4. Why is the discovery of a new Mersenne prime important?

The discovery of a new Mersenne prime is important because it contributes to our understanding of prime numbers and their properties. These numbers have been studied for centuries and continue to fascinate mathematicians. Additionally, the GIMPS project has also helped to advance distributed computing technology and has brought together a community of volunteer researchers.

5. What is the significance of the new Mersenne prime's size?

The new Mersenne prime, M43, is currently the largest known prime number with over 24 million digits. This makes it a notable discovery and adds to the list of the largest known primes. It also means that it has potential applications in cryptography and other areas of mathematics. However, the significance of its size is still being studied and understood by mathematicians and researchers.

Similar threads

  • General Math
Replies
2
Views
1K
  • General Math
Replies
9
Views
1K
  • Linear and Abstract Algebra
Replies
4
Views
4K
Replies
6
Views
4K
  • General Discussion
2
Replies
35
Views
7K
Back
Top