The more prime numbers we find, the harder it gets to find a new one. The latest prime number, discovered using the free Great Internet Mersenne Prime Search (GIMPS) software, is 22,338,618 digits long, over five million digits longer than the last one discovered. The new prime, 274,207,281-1, is also only the 49th known Mersenne prime. The number is so large that a text file containing it occupies 22 MB.
As hardware geeks, we were immediately curious about the machines responsible for the discovery. For the initial proof, Dr. Curtis Cooper at the University of Central Missouri ran GIMPS on a PC running an Intel Core i7-4790 for 31 days straight. His proof was verified independently three times, first by CUDALucas software powered by Geforce GTX Titan Black GPUs running continuously for 2.3 days. A system running AMD Fury X GPUs accomplished the same feat in 3.5 days, as did a system employing two Amazon EC2 servers with 18-core Intel Xeon CPUs.
While primes are important in number theory and cryptography, Dr. Cooper's discovery may not have any immediate application because of its sheer size. The GIMPS software has produced valuable insights unrelated to discovering prime numbers, however. Just recently, mathematicians working with GIMPS uncovered a bug in Intel's Skylake processors.
Anyone interested in a shot at internet glory and a $3,000 discovery prize is welcome to join in the search for the 50th Mersenne prime. Who knows? With that kind of prize money, you just might be able to pay off the electricity bill you'll incur.
[quote<]Anyone interested in a shot at internet glory and a $3,000 discovery prize is welcome to join in the search for the 50th Mersenne prime. Who knows? With that kind of prize money, you just might be able to pay off the electricity bill you'll incur.[/quote<] I remember when the discovery prize was $50,000. I had eight PCs (mix of Pentium 4s and Athlon CPUs) working on finding the Prime numbers. My electric bill ran about $75 a month higher. When the prize was changed so that if I found a new prime I would only receive $25,000 and the other $25,000 would be donated to a charity that GIMPS would select I dropped out. Changing the prize when I had been working on finding one for over a year and then that they get to pick some unknown charity (that I may or may not like) was sleazy.
No it wasn’t sleazy.
You just don’t understand mathematics.
How much time you’ve spend has no bearing on your chances forward.
It was sleazy to just change the prize from $50,000 (to you) to a combination of $25,000 (to you) and $25,000 to a charity you gave no say in.
When they did this I dropped out completely even though I was the eighth highest producer at the time.
This is impressive. Unfortunately, my hardware is all busy folding. And heating my home office. 😀
Even though my hardware is committed already, it’s interesting to hear about this work being done.
I’ll echo Willmore’s invitation to everyone to visit [url<]http://mersenneforum.org[/url<] to find more about primality proving and factoring efforts. Of course, the computation effort side of these things is basically stamp collecting. Mersenne primes may have a little more serious mathematical interest than [url=https://en.wikipedia.org/wiki/Cunningham_project<]factorizations of Cunningham numbers[/url<] (which has actually been called "Sam Wagstaff's stamp collection") or [url=https://oeis.org/A095194<]additions to obscure sequences of semiprimes in the OEIS[/url<], but all these discoveries are basically just fun curiosities. The interesting math is in the algorithms behind these things and the efforts to improve them; the computational effort is largely just a testbed. Specialized algorithms like the Lucas-Lehmer primality test for mersenne numbers may not be hugely mathematically significant by themselves, but general purpose primality provers and factoring algorithms are significant, and tweaks people discover to specialized algorithms may lead to new ideas about general algorithms or to other ideas that advance the field of number theory. An exception where this kind of computation is immediately practical: factoring algorithms, their implementations, and general purpose hardware are now fast enough to break encryption on older smaller encryption keys, especially 512-bit keys. See, for instance, [url=https://en.wikipedia.org/wiki/Texas_Instruments_signing_key_controversy<]the encryption key factorization that allows homebrew firmware to be installed on TI calculators[/url<]. More recently, mersenneforum has seen a lot of new visitors interested in factorization attacks on the poorly made ransomware Teslacrypt. (Malware encrypts your own data, demands you pay the authors for a key- since they chose their keys badly victims generally can and should just factor the key themselves to avoid rewarding bad behavior.) Major advances in factorization algorithms could shake the security world. (Of course that's the premise of the movie Sneakers, for which [url=http://www.usc.edu/dept/molecular-science/fm-sneakers.htm<]they asked a mathematician to consult on a tiny piece of the script. So what the movie mathematician character says actually relates to real math, including the asymptotically best known algorithm for factoring, the Number Field Sieve.[/url<]) But well-chosen keys with modern key lengths are safe for a good long time unless factoring is proven to be in P or people come up with large-scale quantum computers.
The Cunningham Project and Sam are how I got into GIMPS and into GNFS back in the very early 90’s.
And, you’re right, the silly goal is backed by solid math which gets implemented by clever programmers as wonderful bits of code. Each of those things gets more and more useful. Sure, LL isn’t useful for anything but Mersenne testing, but the implementations of it have lead to some very great FFT implementations–which can be used for other, more practical uses.
The main program used for Mersenne testing is called Prime95. The large number math that went into making that program is available as a library which anyone can use to do diffferent kinds of calculations. George’s FFT code is the fastest available on x86 without question. So, there may not be direct uses for Mersenne numbers, there are secondary benefits from the process of finding them.
For anyone interested, Numberphile has two videos about this number, here’s one:
[url<]https://www.youtube.com/watch?v=lEvXcTYqtKU[/url<] They printed the number out in small print on double sided paper, it took three 1k+ page volumes to fit the number. Entirely pointless but still neat. They explain the prime checking process as well.
The GIMPS people tipped off Numberphile ahead of time so that they would have something ready when the press release went out this past Tuesday. I haven’t watched it, yet.
On a side note, we have also know the 49th Perfect Number… 😉
[url<]https://en.wikipedia.org/wiki/Perfect_number[/url<]
31 days on CPU-only doesn’t sound that difficult… Doesn’t sound like there’s too many people searching for Prime numbers these days.
Take a look here: [url<]http://www.mersenne.org/report_top_500/[/url<]
That just factoring the number and the discoverer in question is actually running several hundred systems doing nothing but finding and factoring potential Mersenne numbers.
Actually, Curtis only does primality testing, not any factoring at all. If you look at the chart I linked to, the colums that represent factoring are ECM and FF.
You’re forgetting the magnitude and number of numbers being tested. 31 days doesn’t sound like a lot for a single number, but remember these numbers are now [i<]22MB[/i<] big. When you have twenty two million digits per number, finding the next one that meets certain conditions is difficult. To put this magnitude into perspective, if you had a simple loop: while(true){ i++; } which somehow executed 64 times per clock per thread on a magical 4GHz 64-thread CPU 24/7/365, after one year, i would equal 176,989,936,132,554,752, or 2^57. That leaves 74,207,224 [i<]powers of 2[/i<] left to go to count to this prime. Of course, this only illustrates how large the number is, not how to find a prime. My point is that these numbers are absolutely gigantic, beyond anything you or I can readily comprehend. There are lots of them to test, and if verifying a prime takes even a couple seconds, it's still going to be a lot of time to find the next one. (edited a few times for clearer wording)
I wonder if he also proved his overclock?
STABLE!
I agree. 31 days on a normal desktop computer? Even if each prime is twice as hard to find as the last one, we can get 3 more before it even takes more than a year for normal computer to do it. Much less super computing.
How?! The last prime was almost 16 MILLION powers of 2 ago. 31 days is how long the initial [i<]verification[/i<] took, not how long it took to search for the prime (ie: check one number vs check [b<]many[/b<] numbers around 22 million digits long). This is a nontrivial computing problem. Source: [url<]http://www.mersenne.org/primes/[/url<]
I’m bad at reading.
Either way, that CPU deserves a holiday! I find it fascinating that he did the verification on a consumer CPU, goes to show how good they are.
?
Wow, just wow.
It’s a month just to verify already found and known prime. Finding another, new one, it’s a whole different story. New Mersenne prime may be millions digits further away from 49th one, we may not find it in another couple of years.
Or take it the other way: GIMPS project has been around since 1996 (20 years), and they found only 16 Mersenne prime numbers.
I tried downloading that GIMP software, but all it seems to do is edit images. Anyone know how to get it to find prime numbers?
You need GIMP [i<]PRIME[/i<]. It's like the regular gimp dressed in PVC and leather bondage gear, only he's the king gimp.
Nice. “Gimp Prime” … can be anagrammed to Grime Pimp.
Reminds me of the classic line from Risky Business:
” Miles: I don’t believe this! I’ve got a trig midterm tomorrow, and I’m being chased by Guido the killer pimp. “
They’re hidden inside the images.
Anyone interested in this should head over to GIMPS (www.mersenne.org) and take a look. Joining is very easy and what you contribute is completely up to you–there are different kinds of work that suite different devices (old machine, new machine, GPUs, etc.)
The core of the effort is people who are interested in the math. Yeah, we get a press release out of it and some public attention a few times a decade, but it’s mostly about the math. I’ll admit that there isn’t much practical use for Mersenne Primes, but then again, many things aren’t understood for their real value when they are first discovered. That we have found any use for them is sort of the interesting part. 🙂
Edit: spelling, what’s that?
Prime numbers themselves a good example of something taking a long time between being discovered, and then developing a practical use. Prime numbers have been known about since antiquity, yet didn’t really have a practical use until public key cryptography was invented.
When I read this initially I downloaded the prime just to see what 22 million-plus digits looks like in notepad. Mersenne primes are 2^P-1 with P being a prime number.
The fact that the exponent itself is always a prime number is another interestly thing about Marsenne primes.
That’s the very definition of a Mersenne Prime.
It’s part of the definition and it’s totally proven, but it’s still interesting considering that 2^n – 1 for any positive integer value of “n” is an odd number that on the face of it could be prime.
It’s very interesting that only a small subset of prime exponents have that property though.
Come on over to [url<]http://www.mersenneforum.org[/url<] and talk math with us! Wait until you hear about Perfect Numbers. 😉 Edit: Add this link [url<]https://en.wikipedia.org/wiki/Perfect_number[/url<] Every new Mersenne Prime means a new Perfect Number (and a few other esoteric things.)