
#1
Dec3105, 01:26 PM

P: 62

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 



#3
Jan106, 04:15 AM

Emeritus
Sci Advisor
PF Gold
P: 4,005

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
Jan306, 06:56 AM

P: 62

M43: GIMPS project has found a new Mersenne primeIf 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
Jan406, 12:32 AM

Emeritus
Sci Advisor
PF Gold
P: 4,005

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)? 



#6
Jan406, 02:10 AM

Sci Advisor
HW Helper
P: 1,996

gimps uses what's called pollard's P1 method to look for small factors before it does the Lucaslehmer test. This will find a factor P when P1 is smooth, meaning all the prime factors of P1 are less than some given bound. This works well on numbers of the form 2^n1 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^n1, 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
Jan406, 02:49 AM

P: 62

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
Jan406, 10:47 AM

Sci Advisor
HW Helper
P: 1,996

LLT usually refers to the Mersenne specific LucasLehmer 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
Jan406, 11:28 AM

P: 3,170

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. (: 



#10
Jan406, 11:37 AM

P: 62

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 



#11
Jan406, 12:01 PM

P: 62

The LLT has been discovered by Edouard Lucas and proved rigouresly by Derrick Lehmer. See: Mersenne Wiki and Primality Tests Tony 



#12
Jan406, 12:11 PM

Sci Advisor
HW Helper
P: 1,996

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
Jan406, 12:57 PM

P: 62

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 ... Tony 



#14
Jan706, 02:59 PM

P: 1,877

Haha. That's ridiculous.




#15
Jan806, 03:16 AM

P: 62





#16
Jan906, 10:56 AM

P: 1,877




Register to reply 
Related Discussions  
New Mersenne numbers conjecture  Linear & Abstract Algebra  4  
Relate Mersenne Primes To Sq Triangular Nos.  Linear & Abstract Algebra  6  
A formula of prime numbers for interval (q; (q+1)^2), where q is prime number.  Linear & Abstract Algebra  0  
Factoring Mersenne and other numbers using trimath  Linear & Abstract Algebra  0  
The GIMPS project has found a new Mersenne prime number: M42.  Linear & Abstract Algebra  4 