43rd Mersenne Prime Found

Last month, researchers found the 43rd Mersenne Prime: 230,402,457-1. It’s 9,152,052 decimal digits long.

This is a great use of massively parallel computing:

The 700 campus computers are part of an international grid called PrimeNet, consisting of 70,000 networked computers in virtually every time zone of the world. PrimeNet organizes the parallel number crunching to create a virtual supercomputer running 24×7 at 18 trillion calculations per second, or ‘teraflops.’ This greatly accelerates the search. This prime, found in just 10 months, would have taken 4,500 years on a single PC.

Tags: ,

Posted on January 23, 2006 at 3:07 PM • 36 Comments

Comments

Stephen • January 23, 2006 3:33 PM

Not to discount the signifigance of this effort, but what’s the use of finding these primes short of demonstrating human resourcefulness? Shouldn’t we be using this processing power for folding proteins or the like?

AG • January 23, 2006 3:58 PM

I believe you have talked about this before:
“A 20-year-old hacker pleaded guilty Monday to surreptitiously seizing control of hundreds of thousands of Internet-connected computers, using the zombie network to serve pop-up ads and renting it to people who mounted attacks on Web sites and sent out spam.” – From Yahoo news

Alun Jones • January 23, 2006 3:59 PM

Much of cryptography relies on being able to know prime numbers that are large enough that factoring a multiple of that prime number takes a long long time. In other words, all your cryptography comes out of the search for big prime numbers.

Nick Johnson • January 23, 2006 4:13 PM

Alun: Indeed, but these primes are waaay beyond what’s even concievably required for crypto.

Quite apart from anything else, for most crypto, the machines involved have to be able to generate their own (secret) primes, so a pregenerated prime that takes 7,000 computers 10 months to generate is of no use whatsoever.

Pat Cahalan • January 23, 2006 4:14 PM

what’s the use of finding these primes

Mostly to the point:

This prime, found in just 10 months, would have taken 4,500 years on a single PC.

If we’re going to rely on cryptographic techniques to keep data secure, we should know how easy it is to brute-force attack those techniques.

Nick Johnson • January 23, 2006 4:27 PM

If we’re going to rely on cryptographic techniques to keep data secure, we should know how easy it is to brute-force attack those techniques.

A simple calculation based on the method to be used can do that – you don’t need to actually assemble such an array of machines. And I’m not aware of any crypto scheme that bases its security on the difficulty of finding new and larger mersenne primes.

Pat Cahalan • January 23, 2006 5:28 PM

A simple calculation based on the method to be used can do that

Sure. But you can definitely have a culture of: “This is secure, it would take a single PC 4,500 years to crunch it.”

I guess my point is that unless people see results like this, they don’t necessarily consider implications.

Sure, assembling a 7,000 computer node to attack something for 10 months isn’t trivial, but it provides a reality vector.

But you and Davi are right, it’s essentially an intellectual mountain climbing event.

BLP • January 23, 2006 5:49 PM

It would seem that the point of this is, of course, to secure more grant funding for massively parallel computing.

What you do with your massively parralleled computers is up to your funding sources and/or grantwriters.

jkohen • January 23, 2006 6:06 PM

@Bruce
It wouldn’t hurt to warn the casual reader that the linked file’s size is 9 MB+ big 🙂

Thomas Sprinkmeier • January 23, 2006 7:25 PM

@jkohen

How big were you expecting a 9-million digit number to be?

Anyway, you don’t need to download the file, just evaluate (2**30,402,457)-1 🙂

Evaluating it is much easier than proving it’s primt.

jkohen • January 23, 2006 10:39 PM

@Thomas
I just cancelled the evaluation of that expression after 150 minutes. Either Python’s “bignum”s are a tad too slow, or it isn’t actually more convenient to evaluate the expression instead of just downloading the file.

I know that’s not what you suggested, but it would take a 14400 bps modem about this much time to download the whole file without compression. I’m not even sure how much longer the evaluation would have taken.

Talking about compression…

@Evan
Don’t understimate the power of compression. Longnum here is a file generated by concatenating 10000 pseudo-random digits and a new line. The compressed files were generated using the maximum compression settings for each compressor.
10001 longnum
5238 longnum.zip
5118 longnum.gz
4536 longnum.7z
4359 longnum.bz2

A non-compressed binary representation will also deliver a significant size reduction, given that only ~3.32 bits are required to store each digit. How about 3798102 bytes instead of 9 MB?

Anyway, you all fortunately realized that I was kidding. I was just mocking myself publicly because I had been careless to start downloading the file before even thinking how big it would be, and I had no need for the data itself.

Roger • January 23, 2006 11:19 PM

Yes, its application is mainly pure number theory. One might consider that to be climbing a mountain because it is there, personally I find that far more beautiful, more fundamental, deeper, more lasting than such ephemerata as mountains. But for those whose feet are firmly mired in the clay, there are some (admittedly slight) practical applications.

Advancements in techniques for convolution, developed for GIMPS, have improved FFT algorithms, which are of tremendous practical application.

Another interesting benefit of GIMPS is that after a result is found through massive computation, its correctness can be definitely established with much smaller effort. This makes GIMPS a useful way to test distributed computation systems (and the hardware on which they run). In comparison, testing the validity of results in, say, protein folding, can require a complete research project in its own right.

Comparing GIMPS to Folding@home; well, for one thing, GIMPS is consuming far less computrons than the protein folding project. GIMPS does about 18 TFLOPS, while Folding@home does about 190. And Folding@home is now only one of dozens of medically related distributed computing projects, and then there are others like SETI@home (100 TFLOPS). See, for example:
http://en.wikipedia.org/wiki/List_of_distributed_computing_projects
GIMPS is certainly less frivolous than the Electric Sheep project, which generates random fractal movies!

All of these efforts involve donated computer time, so if someone chooses to support GIMPS rather than Folding@home, that’s his business. And of course, the vast majority of computer owners are not supporting Folding@home or GIMPS or anything else, their PCs are either using their idle cycles to do nothing but generate carbon dioxide, or else are in a botnet distributing spam.

RonK • January 23, 2006 11:26 PM

“…what’s the point…”

Heard about “basic research”, guys?

History indicates that using a certain percentage of funding for advancing knowledge which is not deemed immediately useful produces, in the average, useful knowledge which would probably be difficult to otherwise obtain.

E.g., much of elliptic curve theory wasn’t developed for cryptography…

jammit • January 23, 2006 11:42 PM

Funny thing. Right before I came here, I needed a “burn” test program to test a machine, and downloaded prime95 to do it with. As far as “needing” to crunch big numbers, some of it is bragging rights, some of it is to test a system (burn test), some of it is for a real purpose.

Andy • January 24, 2006 6:15 AM

GIMPS looks like it is solving the same kind of problem as BOINC, though set up to be prepared for issuing a prize. So far, I’ve yet to see these networks used for anything truly practical (many biochemists will tell you that computational protein folding is pretty much a waste of time). But there’s no denying that they could be used for lots of practical things, like cracking RSA keys. I wonder how long it will take, and wonder if they’ll figure out a way to pay people for their CPU time.

In the mean time, I think I’ll go back to searching for space/time ship plans in those 30 million bits of prime.

Oh, and wouldn’t 43.txt have been more efficiently distributed as pure binary plus a simple program to render it as decimal digits?

Andy • January 24, 2006 6:22 AM

…

I stand corrected. The wikipedia page lists some projects that actually do look practical. Hmmm… which one isn’t gonna overheat my AMD processor… ?

be-afraid • January 24, 2006 6:26 AM

This is the sign that the beast is coming.
the number 666 is in 7721 Lines, the cross sum of that is 6 again. We are doomed! 🙂
then again, my birthdate is in there 5 times, so it cannot all be bad. And I am sure that it predicts the next lottory numbers, you just have to know where to look…

Chris • January 24, 2006 8:25 AM

“I find that far more beautiful, more fundamental, deeper, more lasting than such ephemerata as mountains”

Wow. I find it quite exhilirating, and a touch scary, when I am stuck in the middle of a huge Mountain range.

How sure are you that the “large” prime numbers (it is all relative) will always be important? If resolving prime factors becomes easy, will you like mountains again?

DogKebab • January 24, 2006 8:26 AM

Possibly the number itself may not be that useful in everyday life or even in cryptography for a while. But may be the techniques and ideas that were developed to achieve this will be of use in other ways very soon. Blue sky research can have benefits that come not from the end result but from the efforts made to get that end result.

another_bruce • January 24, 2006 9:25 AM

this is old news to fans of mersenne.org, which i mentioned in a comment to bruce schneier’s rogue botnet article couple of months ago.
people say it’s a waste of time. hey, we’re all gonna die, and it’s our time! not curious about prime numbers? not curious about anything? don’t go into space! don’t try to make stem cells! confine yourselves to more mundane terrestrial aspirations, here’s one of mine: making the perfect margarita.

jmr • January 24, 2006 9:56 AM

Um, this is not just an “intellectual mountain climbing event”.

Okay, so it took 7000 computers 10 months. How many computers does Google own? How about the NSA?

We suspect the NSA is ahead of the rest of the world in, among other things, prime factoring. Estimating the resources available to the NSA and evaluating how long it takes for the NSA to factor primes is an important activity. Remember, the knowledge and resource the NSA has eventually become become readily available, given time. When script kiddies with 7000 node botnets start being able to factor financial institution keys, that’s a huge problem.

Secure • January 24, 2006 12:27 PM

“evaluate (2**30,402,457)-1”

jkohen,

“I just cancelled the evaluation of that expression after 150 minutes.”

What did you do to evaluate it? 2**x = 1<<x, where << is the shift left operation. Thus you need only 1 bigint shift left and one bigint subtraction to get the binary representation of the number. Of course, the binary representation is a bit, well, boring… The conversion to decimal ascii could take a while, depending on the algorithm. 😉

Pat Cahalan • January 24, 2006 1:04 PM

@ Secure

Of course, the binary representation is a bit, well, boring…

Decimalist! Anti-binaryte!

/noise

T.Rex • February 2, 2006 2:39 PM

Hello,
Someone here asked if finding new Mersenne primes is useful.
Few is known about how Mersenne primes are distributed. Finding new ones helps to check if the theory matches the reality.
Also, the GIMPS project not only searches new Mersenne primes ; it also searches factors of Mersenne composites. One can either find small factors of big near-10 millions digits Mersenne composites, or one can search for big factors of small Mersenne composites, like 2^1061-1. One can even use prime95 to search for a factor of F14=2^2^14+1, the first Fermat number no factor is known.
People also hope to become famous, one of the few ones who have found such a huge prime number.
Big Mersenne primes can be used to generate random numbers. I’m not sure 9Millions digit Mersenne primes can be used … See: http://www-personal.engin.umich.edu/~wagnerr/MersenneTwister.html
Tony

vikas • February 10, 2006 1:23 PM

you don’t need to open the file. Just right click on the file and hit save target as. It will just take 10 mins. or so.

1/2" • April 24, 2006 1:00 AM

Wow,the size of the numbers & tasks is so daunting and nobody mentioned the roots to Mersenne primes and cyphers. In the apps I know the bigger the better and more rootable hence applicable to comms eg. CDMA,Blue-tooth etc & 802.11.
Tks, very rivetting.
1/2″

1/2" • April 24, 2006 1:09 AM

Wow,the size of the numbers & tasks is so daunting and nobody mentioned the roots to Mersenne primes and cyphers. In the apps I know the bigger the better and more rootable hence applicable to comms eg. CDMA,Blue-tooth etc & 802.11.
Tks, very rivetting.
1/2″

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.