Slashdot Mirror
45th Known Mersenne Prime Found?
An anonymous reader writes "The Great Internet Mersenne Prime Search (GIMPS) has apparently discovered a new world-record prime number. A GIMPS client computer reported the number on August 23rd, and verification is currently under way. The verification could take up to two weeks to complete. The last Mersenne prime discovered was over 9.8 million digits long, strongly suggesting that the new value may break the 10 million digit barrier — qualifying for the EFF's $100,000 prize!"
http://en.wikipedia.org/wiki/Mersenne_prime
Fun.
How we know is more important than what we know.
To what use will this long, long prime be put?
Absolutely none whatsoever. That's the beauty of mathematics.
And you only get 6 digits in prize money? What a rip off. That is only one $digit per 1.67 million prime digits.
When it comes to cryptography, when youbigger the prime numbers you have the harder it is to break the encryption.
According to their own benchmark pages a newer Core 2 Duo E8500 process in less than 21 days. Just recently I know that password cracking programs were written to use GPU's which dramatically increased the performance. Wouldn't writing code to run this on the GPU's result in even faster processing times?
...he asks on slashdot.
From the GIMPS website:
Finding new Mersenne primes is not likely to be of any immediate practical value. This search is primarily a recreational pursuit. However, the search for Mersenne primes has proved useful in development of new algorithms, testing computer hardware, and interesting young students in math.
The beauty is that it doesn't HAVE to be useful.
2^x -1 is never prime if x is not prime. I do believe your number falls under that category.
Agreed. People should be using their extreme CPU cycles for things that matter, like helping the SETI program or running Microsoft Vista.
I'm pretty sure that in the past, the government would pay money for large prime numbers to use for encoding purposes. I don't know if they still do but they used to pay 1000 dollars (I think it was 1000) for primes over 100 digits.
And work backwards, that will find the largest much faster than starting at zero.
You seem to misunderstand the meaning of prime. Either that, or you're a horrible comedian. In either case, 77 isn't prime, and neither is 77777777.
However, even if a string of 7's were prime, that may not be enough. As stated previously, if n = 2^x - 1 is prime, then x must be prime. However, the converse is not true. That is, x being prime does not guarantee that n is prime. E.g., if x = 11, then n = 2^{11} - 1 = 2047 = 23 x 89.
That depends. If it's over 10,000,000 digits then it will be cashed in for $100,000.
Slashdot: Failed Car Analogies. Amateur Lawyering. Anecdote Battles.
You shouldn't think like that. Just think about your question, seriously. Whatever we do is pointless and useless and everything will be destroyed eventually through the heat death of the universe.
That being said, all that is important is that you have fun doing whatever you do. Believe it or not, some people really dig maths. Also, it's one more thing the species knows.
But when it comes to primes in the 10 million digit range (I couldn't even guess how many bits you would require for a number that large)
About 33 million bits ( ln(10)/ln(2) = 3.3219 ) or 4MB.
Sure, you are excited now, but I predict you will look back on this moment with indifference once the 46th is discovered. For now, I'm going to keep the champagne on ice.
I Heart Sorting Networks
...even!
Actually for a number of 2^n-1 to be prime, n must be prime also. There is no chance that 2^32,582,658-1 is prime.
>> To what use will this long, long prime be put?
We'll sell it into slavery on the Venusian mining colonies, what else you fool?
My new lock combination...
I guess some of us have different standards on beauty...
5 years ago few believed that a simple prime number could be calculated to 10 million digits. There was a lot of scepticism that a prime number could be calculated so large. A prime number, calculated to 10 million digits?? pfft. But now, 5 years later GIMPS has calculated Mersenne primes over 9 million digits using computers of all ages, all over the world. That's because GIMPS is scientifically proven to work. It's not a gimmick.
...
(Random interviews)
Q: What happened when you participated in the GIMPS project?
A: Ah.. It got bigger.
Q: And you're not embarassed to say that?
... why the EFF considers it worth $100,000 of donated funds to pay someone for finding a 10,000,000-digit prime number. That is not what my donations were intended to do.
Go fix warrantless wiretapping, then go looking for prime numbers, kthxbye.
Since this is a particularly good prime, we should
standardize on it. That way we wouldn't have to
find our own ones every time we want to use RSA.
"Physics is like sex. Sure, it may give some practical results, but that's not why we do it." - Richard Feynman
I'm guessing it's the same logic at work here.
The submitter or editor could have at least typed the number into the summary. Lazy bastards.
Because doing it by hand is a real bitch and a half. Doing it by hand in moon or candle light sucks worse, I must add.
Navicula hydraulica plena anguilarum est. Omnes castelli tuus nostri sunt. Ed elli avea del cul fatto trombetta.
Oblg.
http://xkcd.com/435/
This is not a sig.
You forgot to divide by 8...bits != bytes
...is a list of all the prime numbers whose length in number of digits is also a prime number as well. I wonder if anyone has found any really big ones of those.
Because it's 2^n-1 it'd be 1111111....1111111 (the prime number is entirely made of 1s in base 2). So there's way less than 31MB of information in the number
// MD_Update(&m,buf,j);
It goes towards the enormous knowledge on prime number theory.
The problem of if there is a pattern to the sequence of prime numbers is unknown. That is, if I ask you what is the 69th prime number, the only known general algorithm is to computer the 1st prime, 2nd prime and so on until the 69th prime. And, also there are unsolved problems with Mersenne primes as well.
So, if someone comes up with a good theory, then it's good to have some big examples.
And, in case you didn't know, prime number theory is used in cryptography.
"Is that a Mersenne prime in your pocket or are you just happy to see me?"
My friends and I wrote a unique prime number sieve, using previously unknown numerological techniques (exploiting digital roots).
You can find our sieve here:
http://jessicalogsdon.com/page5/page5.html
We are currently turning our sieve in a method for rapidly factoring semi-prime numbers. Digital root mechanics have certain properties that make it easy to identify semi-prime candidacy positions in a by-9 table of the natural numbers.
A PDF at the bottom of the above-linked site explains our latest investigation of solving for [p, q] where n = p*q. The source code on the page is our prime sieve implemented in Perl.
Big Money! No Whammy! You, too, could become a hundred-millionaire M.O.H.'ing RSA to the ground!!
-=/\- Jizzbug -/\=-
On slashdot, even the submitters don't RTFA apparently:
Or you didn't read it properly: the bit about being just short of 10 million is about the 44th when it was new, not the new new prime.
I do IT-support in the school district...let me tell you:
The kids were in a veritable state of mathematics riot today.
Smoking pot, getting laid, and blowing off responsibility is so not punk rock.
God...do these guys realize how embarrassing they make adulthood?
That has to be one of the best penis pill ad spoofs I've ever read. Kudos on that classy rewrite.
My only question is where the reasonably attractive blond chick who blinks too damn much comes in.
Try not to take me more seriously than I take myself.
You must not be new here
Make SELinux enforcing again!
Depends. Is your day job working as a mathematician? :)
I think the real question is why it is worth $100k. I'd sure be interested to know, especially seeing that my system can probably attempt to find prime numbers pretty damn quick if it's a threaded app.
How are sites slashdotted when nobody reads TFAs?
So this is like math's version of Paris Hilton? Pretty but useless?
basically, they distribute the prize to contributors...currently $50,000 would go to you
One last thing: Sometimes I wonder; "Is that someone's signature? Or do they type that at the end of each post?"
doing it by hand would be like building the pyramids, by yourself.
it's not a weekend project, just writing down all the numbers from 1, to the number composed of at least 9 million but possibly ten or eleven million digits long... much less then dividing that number by every number from 1 to the number of the same length to make sure it is only evenly divisible by itself, and 1.
i repeat myself it's like trying to build they pyramids by yourself. or even better, trying to build a four lane highway by yourself. I remember hearing about a guy from Duluth Minnesota, who had been trying to build a highway the most direct route between Fargo, ND and Duluth, MN, and he actually started on the Duluth side, i know he didn't get far, but Duluth Minnesota is one of those 'rare' towns that was booming about 100 years ago, but then started shrinking (i forget when) and has never really completely recovered.
the guy started on his quest to get the highway built believing a direct route to Fargo would increase trade and tourism and what not (it would save on average an hours drive each way)
but i think he finally died, having completed somewhere between 12-40 miles of highway.
today's PCs are like having millions of number crunching slaves with never ending papyrus scrolls, there are things computers can do that a human being would never complete if they lived a million years. and even with those millions of number crunching slaves some things take a long time to compute.
the point being, the reason why people do these things with computers is because computers are the only thing that can do them, and to be the first to do something vastly unimaginable by normal standards. kinda like, 'why did we shoot a robot lander to mars?' instead of say, making beer free for everyone in the united states for a day.
https://www.gnu.org/philosophy/free-sw.html
I saw this joke posted on slashdot like, less than a week ago,b ut it's so relevant to the discussion ... fuck it.
"An engineer, a physicist and a mathematician were all staying in a hotel, when each of their rooms individually caught fire. The engineer did some basic math, flooded the floor and said, "it is out." The physicist did more complicated math, used just precisely the amount of water needed to put out the fire and said, "It is out." the mathematician did a lot of complicated math, said, 'I HAVE SOLVED IT!' and went back to bed."
Non impediti ratione cogitationus.
Testing a single candidate Mersenne prime takes a month of straight computation on a single 2.4 GHz Pentium 4 (assuming a 10 million digit prime, which would be the minimum to win the prize). This assumes the use of only one core, but you'd need at least 100 cores to make it anything resembling "quick" (~7 hours), if you could even parallelize the procedure that much.
Never mind the fact that only about one in 150,000 exponents will yield a prime, meaning that on average, 150,000 months of computation is required for a single prime to emerge, and furthermore, finding giant Mersenne primes is easier than most other kind of primes. So, I don't think your computer will find these giant primes "pretty damn quick".
Pessimism aside, I think this is a pretty impressive achievement considering that GIMPS doesn't have nearly the power of larger efforts like Folding@Home (GIMPS has around 500 GFLOPS while F@H has around 3372 TFLOPS, or 3372000 GFLOPS).
Yes, half of it.
If you were to find a 10,000,000 digit prime today the above rules imply that $3,333 would go to Michael Cameron, discoverer of the 39th known Mersenne prime, $3,333 would go to Michael Shafer, discoverer of the 40th known Mersenne prime, $3,333 would go to Josh Findley, discoverer of the 41st known Mersenne prime, $3,333 would go to Dr. Martin Nowak, discoverer of the 42nd known Mersenne prime, $6,667 would go to Curtis Cooper and Steven Boone the discoverers of the 43rd and 44th known Mersenne prime, $5,000 would go to GIMPS, $25,000 would go to charity, and $50,000 would go to you.
This is great news, I've been crunching Mersenne numbers myself and it's nice to finally see a potential >10M digit one.
You're complaining?
I studied psychology!
:(
Those bastards! Now I have to change my luggage combination again.
Well, there's spam egg sausage and spam, that's not got much spam in it.
Aaah yes, the xkcd that made me stop reading xkcd.
As a chemist, i felt a bit upset at the elitist attitude of the comic, and no I do not think that biology is 'merely' applied chemistry, and therefore somehow less 'pure'.
Cry me a river, impure professional.
Mersenne primes are almost completely useless. I used one to win a programming contest in college involving finding the largest prime number though. Unfortunately the moderator posted my number without the last digit and everybody complained it was divisible by 2.
You stopepd reading a comic because it made fun of you? I'd hate to live in that sad boring dreary life of yours, Monday, Wendsday and Friday that comic makes fun of me and I love it for it.
If you can't laugh at yourself then you have no right to laugh at anyone else.
I may agree with what you say, but I will defend to the death your right to face the consequences of saying it.
That's ridiculous. Being useless is not what makes math beautiful. There are plenty of useless things that aren't beautiful.
A lot of them post here.
echo -e 'global _start\n _start:\n mov eax, 2\n int 80h\n jmp _start' > a.asm; nasm a.asm -f elf; ld a.o -o a;
Becuase it is there and becuase we can. why bother to do anything at all? In a hundred years nobody will care or remember you for anything you have done at all during your lifetime, perhaps you should just go crawl back into bed and stay there for the rest of your life? You will have the exact same impact on the rest of the universe that you would have otherwise. While your doing that the rest of us will 'waste' out time discovering the universe around us, it may not server any purpose but we choose to do it and we feel better for it.
I may agree with what you say, but I will defend to the death your right to face the consequences of saying it.
I for one am glad that the EFF isn't using my donations for this award, beautiful mathematics or not. When I donate my hard-earned money to the EFF, I expect them to use it for something worthwhile. From TFA:
Prize money comes from a special donation provided by an individual EFF supporter, earmarked specifically for this project. Prize money does NOT come from EFF membership dues, corporate or foundation grants, or other general EFF funds.
Ah, arrogance and stupidity, all in the same package. How efficient of you. -- Londo Mollari
Prime numbers routinely prove to be useful.
I, for one, will be using it for my hashtables, thank you very much.
If you can read this, I forgot to post anonymously.
My favorite incarnation of that joke has the mathematician saying "THERE IS A SOLUTION!"
:)
It's amazing to me that it's possible to know that there is a solution, but not know what it is. Kudos, math people
Life is rarely fair. Cherish the moments when there is a right answer.
Close, but she's only pretty useless.
If you can read this, I forgot to post anonymously.
Hey, at least it wasn't computational linguistics.
I didn't see your response, so I wrote my own instead of moderating yours like I should have. If anything, laughing at yourself should be easiest of all since you are more likely to get the joke given an intimate knowledge of its subject matter. =)
Yeah they even can provide complicated proof that there's a solution, while being unable to provide one.
:)
Consultants on the other hand can provide expensive proof that there are solutions, while being unable to provide one.
"Physics is like sex. Sure, it may give some practical results, but that's not why we do it." - Richard Feynman
Which is why Richard Feynman is known as the father of quantum mechanics.
Very Wrong
Large prime numbers are used in cryptography because it gives you massive amounts of digits that are not divisible by any other number. There's types of crypto that use multiple large prime numbers to build the keys from. If you use one of these as your seeds it will take a long time to crack anything encrypted as the number is huge and has no smaller factors. At 10 million digits you're going to take a long time to "guess" what it is.
Another fun relationship is between Mersenne Primes and Perfect Numbers, numbers whose factors add up to themselves.
If 2^n-1 is prime, (2^n-1)(2^(n-1)) is perfect (and has a distinctive pattern of digits in binary, to boot...). The proof in this direction is easy. Proving that all even perfect numbers are of this form is a little harder, but doable.
The hard one is proving whether or not there are any odd perfect numbers, and, if so, what form they might take. Nobody has done this yet.
...laura
>if you could even parallelize the procedure that much
You can't. Multiple cores are of no help in speeding up a prime number search like GIMPS. Each iteration of the test requires the results of the previous iteration. All multiple cores do is allow you to run multiple copies of the software (one per core) in order to allow a machine to test more than one prospective prime at a time.
FWIW, I run two copies of the GIMPS software on an E8400 processor, one copy on each core. And last time I did a benchmarking check on it, its currently taking 26 days and a few hours to fully test exponents in the 42,000,000 range.
I want a new quote. One that won't spill. One that don't cost too much. Or come in a pill.
Mathematician #1: How are we going to find the 46th Prime?
Mathematician #2: Bring out the GIMPS.
Mathematician #1: The GIMPS is sleeping.
Mathematician #2: I guess you're going to have to wake him up then.
The manifest absurdity of it is too obvious to require explanation
My favorite incarnation of that joke has the mathematician saying "THERE IS A SOLUTION!"
Try: "A solution exists." For the punchline to work best, use the math lingo as it would be used in a real proof. Also, since he was a theoretical mathematician, he didn't do "a lot of complicated math", he "looked at the fire, looked at the bucket of water [*1], concluded that 'a solution exists', and went back to sleep".
It's amazing to me that it's possible to know that there is a solution, but not know what it is. Kudos, math people :)
Heh -- when you put it that way, it does seem kinda weird, but it's really not that hard to explain how it works: the key is that the task of figuring out whether or not a solution exists for one problem can itself be taken as an entirely different problem, so if you just solve that one instead of the original one, there you are. And those "meta-problems" tend to be both much easier in terms of actual computation required and much more "interesting" [*2] in terms of conceptual effort required, which is why mathematicians prefer to focus on them. And yes, it works recursively (figuring out whether or not it's possible to determine whether or not a solution exists for a particular problem, and so on...)
[1] one of which, the GP forgot to mention, was conveniently in each room
[2] in math lingo, i.e., "harder" in normal terms
David Gould
main(i){putchar(340056100>>(i-1)*5&31|!!(i<6)<< 6)&&main(++i);}
Put another way, mathematics is to physics, as masturbation is to sex.
I hate printers.
At 10 million digits you're going to take a long time to "guess" what it is.
If there is only one known prime number with 10 million digits, then I reckon I could guess this one quite quickly.
U1NCaVpYUWdlVzkxSUhkcGMyZ2dlVzkx SUdoaFpHNG5kQ0JpYjNSb1pYSmxaQT09
No, that would be Max Planck.
That's not Picasso, that's Kandinsky!
Must.... resist... mother joke...
Not when they are this big. It'd be too hard to work with and there are too few known primes this large for it to be secure.
After reading that strip, I went to the wikipedia article on Deconstructionism, read it, and then still had no idea what Deconstructionism was. I'm pretty sure it doesn't actually mean anything.
Quantum Physics has many fathers. Classical physics is a bit of a slut.
It's been a long time.
See, this is what happens when psychologists try to be funny. There's always someone who finds it insightful.
Perhaps you could use a number-theoretic fft (using modular arithmetic instead of fp arithmetic) on a gpu to avoid the errors accumulation. Although old gpus only processed single precision fp, new gpus can process 24-bit integer multiplication at full speed as well (at least for nvidia's cuda). You probably gain a little bit of accuracy using NTTs vs single precision FP FFTs (where you probabaly need a few guard bits to avoid subtraction errors) which is likely an exponental speedup with these types of algorithms.
Of course the double precision arithmetic is only somewhat slower than single precision on GPUs, but consumes twice the register space (so on actual algorithms, it runs quite a bit slower because of this). Right now, GPU ffts are quite a bit faster than CPU ffts, but not yet 10x (unless you have a very large GPU and a fairly ordinary CPU) if you copy the data back to the CPU every time after an fft, but if you leave the data in the GPU and code the rest of the digit-convolution algorithm on the GPU, I'll bet it isn't that far off of 10x on average.