New Largest Prime Found: Over 7 Million Digits

Jeff Gilchrist writes "On May 15, 2004, Josh Findley discovered the 41st known Mersenne Prime, 2 to the 24,036,583th power minus 1. The number is nearly a million digits larger than our last find and is now the largest known prime number! Josh's calculation took just over two weeks on his 2.4 GHz Pentium 4 computer. The new prime was verified by Tony Reix in just 5 days using only half the power of a Bull NovaScale 5000 HPC running Linux on 16 Itanium II 1.3 GHz CPUs. A second verification was completed by Jeff Gilchrist of Elytra Enterprises Inc. in Ottawa, Canada using eleven days of time on a HP rx5670 quad Itanium II 1.5 GHz CPU server at SHARCNET. Both verifications used Guillermo Ballester Valor's Glucas program." Read on for more on the discovery, including how you can help find more primes.

Gilchrist continues "If you want to see the number in written in decimal, Perfectly Scientific, Dr. Crandall's company which developed the FFT algorithm used by GIMPS, makes a poster you can order containing the entire number. It is kind of pricey because accurately printing an over-sized poster in 1-point font is not easy! Makes a cool present for the serious math nut in your family.

For more information, the press release is available.

Congratulations to Josh and every GIMPS contributor for their part in this remarkable find. You can download the client for your chance at finding the next world record prime! A forum for newcomers is available to answer any questions you may have.

GIMPS is closing in on the $100,000 Electronic Frontier Foundation award for the first 10-million-digit prime. The new prime is 72% of the size needed, however an award-winning prime could be mere weeks or as much as few years away - that's the fun of math discoveries, said GIMPS founder George Woltman. The GIMPS participant who discovers the prime will receive $50,000. Charity will get $25,000. The rest will be used primarily to fund more prime discoveries. In May 2000, a previous participant won the foundation's $50,000 award for discovering the first million-digit prime."

In case you missed it

[barcodez]

The GIMPS [mersenne.org] Project found this prime. You too can contribute by downloading the client (for various OSes).

Thought I would drive the point home as this is a great DC project that doesn't receive half the attention of some of the more dubious DC projects...

Re:I hate to be a pushover...

[DarkHelmet]

A mersenne prime is the easiest form of prime to prove (easy being least computationally expensive).

So right now, this is the largest proven prime number at this point in time. It is 1,000,000 digits larger than the next largest known prime number, (which is also a mersenne prime).

There very well may be a day where primes this large will be used for encryption purposes. But this may be a long way off.

Keep in mind, that so much of the underpinnings of today is based on mathematics from the 1600's to the early 1900's. The math we pursue today will most likely reach a practical application point next century.

History of Prime #s

[NEOtaku17]

http://www-gap.dcs.st-and.ac.uk/~history/HistTopic s/Prime_numbers.html

Re:I hate to be a pushover...

[azav]

And why do we care about the perfect numbers?

In the end, what does this get us?

Please elaborate for those of us who need a reason to care about primes, perfect numbers & the like.

Re:Primality is in P

[ezzzD55J]

True, but that's for general, unstructured numbers, while mersenne numbers are structured so that they're much easier to test for primeness than other numbers of that size. IANANumberTheorist, but it's such a huge difference that I doubt the general polytime test will ever be faster than the special mersenne test...

BTW wasn't the polynomial order 6 whenever a unproved-but-likely hypothesis was true?

Re:Primality is in P

[You're All Wrong]

Primality tests for numbers of the form k*b^n+/-1 have always (since Proth's time) been poly time, in fact O(n^(2+eps)).

http://primepages.org/

'proving'

YAW.

Re:So an Itanium GHz is worth less that a P4 GHz?

[alehmann]

Among other things, Glucas is writen in C and Prime95 is mostly x86 assembly that's heavily optimized for SSE2 and the P4.

Not to mention that you can't expect the threading to scale perfectly. I'm surprised that there are any gains at all because the LL algorithm is so sequential. I remember hearing that Glucas could have done it in half the time on that machine if it had been optimized for NUMA, though.

Re:I hate to be a pushover...

[Anonymous Coward]

Not sure about perfect numbers, but primes are used in certain public-key cryptography schemes like RSA. Of course a prime as large as that mersenne prime isn't of much use in RSA as the primes they use there are never usually bigger than 512 digits (4096 bits) which is more than adequate if chosen with care.

Oh, and more specifically (correct me if I'm wrong, I probably am) using mersenne primes (ie primes of the form 2^p-1) prevent certain factorization algorithms from succeeding. And if you manage to factor n (part of the public key in RSA) you've broken the cipher and can obtain the private key and decipher.

6 years

[GISGEOLOGYGEEK]

Been running prime 95 for 6 years now.

Started with a p120 laptop, at times had a dozen computers teamed up.

In that time .. ive found no primes but the work ive done would have taken 307 years for a p90 computer to match... a p90 being the 'zero-point' computer when the project started.

Re:I hate to be a pushover...

[WalksOnDirt]

"Are Mersennes really the easiest numbers to prove prime?"

Yes, because of the Lucas Lehmer primality test, which you can google if you want to see the details.

The standard proof of primality involves factoring the number one less than or one greater than the prime. Obviously, the number one greater than 2^p-1 is easily factored, which is the basis of the test.

Want to see the number?

[tjackson]

$ dc -e '2 24036583 ^ 1 -p' > bigprime

Re:text file?

[Anonymous Coward]

1 character = 1 byte (in ASCII)
10,000,000 bytes = 10 megabytes (or 9.54 binary megabytes)

just generated it...

[Anonymous Coward]

Thanks to the suggestion for...
dragon $ dc -e '2 24036583 ^1 -p' > bigprime
(took all of 10 minutes to generate on dual p4 2.4 RHEL box)

It is...
dragon $ cat bigprime | wc
104866 104866 7445464 :-)

dragon $ more bigprime
2994104294041571720890489263404469382573 6772297541 8473547677348600097\
6402211007410262658651099123 2085849334415641521263 5335213499669984946\
4660024345642470272577169564 2662105261107741637995 6346589355834130669\
1793645554900420589512627118 1099996307160208959114 6249605845552251245\
1750406146467967427758141698 7797735189577892265233 9915229521619514779\
5568313648450268950958240527 1220741611859625359434 4535443908358061475\
9525813062523939655643872135 6880887010955400164710 2077512671720670861\
1484703783801582301475946984 2856323336793806285343 7133547200496603279\ ... cut ...

596042138740223572105833031297130060155848247331 65 5040635746326190400\
4552714727628399333714490840 1115064186802797305085 0098493495965965353\
0757538248731674269131691718 8885630947927139764390 6093267419703016252\
0971632898561173793986132063 0694859231047623622621 9731381759341727521\
3175667765215893946023476293 0906270990621862597287 8493025170887476672\
7408309233371335704722292567 8801564700107406013708 5901832324495455374\
3897283900425045692486553784 8448729599792041549432 0295787114054394490\
4048445691846654931066223037 4225623854962949493299 0957491791132574973\
6793183564954933262413429503 7485542595520771846437 8183256423142526858\
6870398005560312691184129150 67436921882733969407

Ends in 7. Yep. Looks prime to me. ;-)

Just kinda working the list from the website... the difference between the primes always *seem* to be EVEN (after the first couple). Hmm...

Re:So an Itanium GHz is worth less that a P4 GHz?

[Markus Landgren]

And a P4 GHz is worth a good deal less than either a P3 or Athlon GHz...

No, it's not. Not for finding Mersenne primes anyway. You see, the relative performance of different CPU types depends on the kind of work being done.

The benchmark charts at mersenne.org show that a P4 1800 MHz beats the Athlon 64 3400+ running at 2200 MHz. Even my own old P4 1600 MHz comes in ahead of the AthlonXP 3200+ running at 2200 MHz.

So, my guess is that there is some kind of work where the Itanium beats the P4 and the Athlon. Who knows, maybe this cluster was not bought to run MS Word or UT2004, or some other application where the Athlon beats the crap out of an Itanium or a P4?

Re:I hate to be a pushover...

[Markus Landgren]

I am not sure about any use for perfect numbers, but the Mersenne primes themselves can be used to create random number generators with extremely long periods [ox.ac.uk]. That takes some additional work, although not as much work as finding this prime among tens of thousands of composite candidates.

Re:oye. it is not the largest prime ever

[Anonymous Coward]

2^24036583-1 + 10^1000000000 is divisible by 13, therefore it is not prime.

What kind of math background do you have?

Re:What a good OS X client for this?

[koekie]

Since the main routines of Prime95 are in intel assembly it can't be compiled for the Mac. For the mac you can use GLucas (which was also used in the 2 verification runs), you kan find it at http://glucas.sourceforge.net/ [sourceforge.net]

Re:Verification

[tmyklebu]

Why? It's not as if doing the verification with different algorithms will lessed the probability of a mistake; a quick Google search shows that Glucas is a deterministic algorithm for testing primality of Mersenne numbers.