Slashdot Mirror
New Largest Known Prime Number: 2^57,885,161-1
An anonymous reader writes with news from Mersenne.org, home of the Great Internet Mersenne Prime Search: "On January 25th at 23:30:26 UTC, the largest known prime number, 257,885,161-1, was discovered on GIMPS volunteer Curtis Cooper's computer. The new prime number, 2 multiplied by itself 57,885,161 times, less one, has 17,425,170 digits. With 360,000 CPUs peaking at 150 trillion calculations per second, GIMPS — now in its 17th year — is the longest continuously-running global 'grassroots supercomputing' project in Internet history."
Actually it would be 2 multiplied by itself 57,885,160 times, minus 1.
2^4-1 = 16-1 = 15.
5 * 3 = 15.
Go read it again.
You might want to read that link again. Not any number 2^n-1 is prime. Just that a prime in the form of 2^n-1 is called a Mersenne prime.
Sigh, you need to go back and read the link you posted:
"Though it was believed by early mathematicians that Mp is prime for all primes p, Mp is very rarely prime."
I see a problem though: According to wikipedia, "Some definitions of Mersenne numbers require that the exponent n be prime."
Some? Huh? Mathematics does not deal in disputed definitions! I've never heard before that Mersenne numbers need a prime exponent.
It's really just a matter of semantics. If n is composite, then 2^n - 1 cannot be prime.
There isn't a 100% correct primality proving method for general numbers that's anywhere near as efficient as the Lucas-Lehmer test for Mersenne numbers of the same size.
Mathematics does deal with a lot of "disputed" definitions. Mathematics deal even with a lot of "disputed" logic and "disputed" interpretations. Read about the axiom of choice, set Theory in general, Constructivism (mathematics) and Finitism and you will understand that things get quite more complicated than you thought.
Yup, was totally wrong about this. Euclid's Proof of the Infinitude of Primes suggests doing something like this (multiplying all primes and then adding 1), but it doesn't work in generating new primes.
They're all right here: http://mersennewiki.org/index.php/List_of_known_Mersenne_primes
Since the only known perfect numbers are derived from Mersenne Primes, this means there are also now 48 known perfect numbers. Interestingly, this property of Mersenne Primes was discovered by Euclid about 2000 years before Mersenne was born (time machine, anyone?). Finding a non-Mersenne perfect number would be a huge accomplishment.
Have you read my blog lately?
number of the form 2^n-1 are Mersenne numbers which are much more likely to be prime than a randomly chosen odd number. Also, we have "simple" test for these number to weed out many Mersenne numbers that are not prime. Once you have a Mersenne number that passed the "simple" primality test, there is a good chance that it will really be a prime number.
Mersenne primes have a structure that makes it possible to test primality for very large numbers; there's no way to test whether unrestricted numbers of that size are prime (it's theoretically possible, but there aren't enough computing resources on the planet.)
I used to run the GIMPS search application back in the 90s; you really really don't want to run it on a laptop on batteries, especially with the battery technology of the time, and eventually I decided that my laptop didn't have enough horsepower to bother, compared to desktops that could run GPU-based calculations.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Though it was believed by early mathematicians that Mp is prime for all primes p, Mp is very rarely prime. In fact, of the 1,622,441 prime numbers p up to 25,964,951,[5] Mp is prime for only 42 of them. The smallest counterexample is the Mersenne number
Mv11 = 2^11 1 = 2047 = 23 × 89.
Hmm, the humour and sarcasm seem to have been be lost on you.
Hey, has anyone told you that your post is wrong yet?
"Our two-party system is like a bowl of shit looking at itself in a mirror." - Lewis Black
Mathematics may not deal in disputed definitions, but Wikipedia certainly does.
111 1111 1111 == 2047 == 23 * 89
Funny how many assertions here that number disproves
There is a very fast primality test for Mersenne numbers, the Lucas–Lehmer primality test.
2^n+1 is prime only if it's a Fermat prime, n=2^k. None of these are known to be prime for k>4, and there probably aren't any more, whereas there are probably infinitely many Mersenne primes.
If you could find new primes that easily then internet banking wouldn't be secure (well...as secure as it currently is, which is "enough for the insurance companies").
No, it relies on factoring being much more difficult than multiplication. That is, if I have two large primes p and q I can trivially calculate p*q = n, but you can not easily find p and q from n. Being able to generate primes quickly doesn't give you anything.
Live today, because you never know what tomorrow brings
Actually they are a lot less likely to be prime than any random odd number, only 48 are now known and all have been tested up to above 13 million digits. But yes they are very easy to prove prime compared to "random" numbers of no special form, I *think* it was proven mathematically that there is no faster proof possible, but don't hold me to that. The highest "random" number proven to be prime is only 26,642 digits vs 17 million for this new mersenne prime. There are numbers of other special forms that are also "easy" but not as easy to prove, highest one proven is 3.9 million digits. They don't look for primes 2^n+1 because they are always divisible by 3 so they are never prime. They are looking for primes (2^n+1)/3 however, they are called Wagstaff primes, but again they are harder to prove than mersenne numbers.
"There are 10 kinds of people in the world. Those who understand binary, and those that don't."
This new number is 2^57,885,161 - 1, so naturally it has 57,885,161 digits, all of them 1. A simpler example: 2^5 - 1 is a Mersenne prime. Written in binary it's 100000 - 1 = 11111.
Oh! You meant that it has 17,425,170 decimal digits. Booooooooring!
Yes. The LL test only works on Mersenne numbers--numbers of the form 2^p-1 where p is prime. The LL test is not statistical. It can determine if a given mersenne number is prime or not without any doubt.
To protect against errors, GIMPS (Great Internet Mersenne Prime Search) uses a variety of double checks to ensure no number if mistested. Any number that passes the LL test is double (and sometimes triple checked) to verify that there wasn't a hardware or software error that caused a false positive. I had the honor of performing the double check of a record Mersenne prime some time ago.
I wonder if 2^(2^57,885,161-1)-1 is also prime.
Stop wondering and start dividing. Call us when done.
https://app.box.com/WitthoftResume Code: https://github.com/cellocgw
Using CPUs is generally a simpler approach when building a distributed system like this. Yes, per individual computer GPUs can be more efficient, but you also need to look at the number of assisting nodes you're going to get, and this number may (I'm guessing) be higher if you let any old CPU join the party rather than fewer high-end GPUs.
Please consider this account deleted, I just can't be bothered with the spam anymore.
Optimus Prime is bigger.
Facts take all of the premium out of arm waving - T. Reynolds
Now I have to find a new combination to my luggage. Again.
Well, there's spam egg sausage and spam, that's not got much spam in it.
It is far easier to test Mersenne numbers for primality than general integers, thanks to the Lucas-Lehmer primality test. Weeding out composite Mersenne numbers by trial factoring is also faster, thanks to a theorem that eliminates most of the candidate factors.
As for numbers of the form 2^n+1, it's easy to show that if 2^n+1 is prime, then n must be a power of two. Such numbers are known as Fermat numbers, and there is also a fast primality test (Pepin's test) for numbers of this form. But because of the power of two in the exponent, each Fermat number is double the size (in terms of the number of digits) of the previous one. It doesn't take long before you exceed current computing capabilities. And so far, all the Fermat numbers we've managed to test have turned out to be composite, apart from the first five. Furthermore, it is conjectured that there are only finitely many Fermat primes, so it's possible we've already found them all. On the other hand, it is conjectured that there are infinitely many Mersenne primes.
I'm just trying to weigh the energy consumption versus potential benefit. The GIMPS homepage does a terrible job of explaining why (I'm not suggesting that there is no reason to do this) and a linked FAQ is hardly better ( http://primes.utm.edu/notes/faq/why.html ). Can anyone provide a better answer or instruct those running the GIMPS homepage to do so?
Yes. And both are used for GIMPS.
See the Mersenne Forum's GPU Computing sub-forum for details.
There are, however, many more CPUs than GPUs out there, so most of the work is still done by CPUs. Two different GPUs using different software (CUDALucas) were used to confirm that 2^57,885,161-1 was prime, in addition to two other CPUs (one using different software than the GIMPS standard Prime95/mprime).
I've got a problem with that WW meme.
In the movie, that was NOT WW's final judgement. It was a final test of Charlie's character. Charlie contested WW's brusque send-off and ended up owning a chocolate factory.
What kind of lesson is this teaching our kids?!
the preceding comment is my own and in no way reflects the opinion of the Joint Chiefs of Staff
To be a little more clear about this, primality proving algorithms are generally constructed to produce a certificate that makes it easy to verify that the algorithm was indeed executed completely and indeed proved primality, and these certificates themselves are as difficult to forge as the proof itself.
"His name was James Damore."
Mersenne primes have a structure that makes it possible to test primality for very large numbers; there's no way to test whether unrestricted numbers of that size are prime (it's theoretically possible, but there aren't enough computing resources on the planet.)
Basically, it is much easier to find a proof that p is prime (if it is indeed prime) if you have a complete factorization of p + 1. For this number as for all Mersenne primes, the complete factorization is quite obvious.
If the exponent is not prime, then the number will not be prime.
I don't do HTML, I'll use the symbol ^ for exponent (I don't do C either). Let's suppose c = a*b, then 2^c - 1 is divisible by both 2^a - 1 and 2^b - 1. (That's true with x instead of 2, the difference being 2^1 - 1 is 1 which is not prime.) Whether the definition requires primality or not, mathematics dictates that the exponent must be prime.
Yeah, it's better to get the math completely wrong.
Well, it's difficult to get the math partially wrong!
Ezekiel 23:20
I wonder what the energy use of this project has been? 17 years? How many megawatthours? And what would be the 'carbon footprint' ?
its an aesthetic discipline not an objectively useful one.
alot of it turns out to be useful, sometimes hundreds or thousands of years after its first 'discovery'.
Quaternions would be a perfect example, imaginary numbers another.
so right now we have no idea what the usefulness of finding high primes is.
but in 200 years it might allow us to calculate the control points necessary to create an anti-matter damper for protonium neon flux casings in hyperdimensional warp transferrence beam generators.