Slashdot Log In
45th Known Mersenne Prime Found?
Posted by
samzenpus
on Wed Aug 27, 2008 07:18 PM
from the really-big-number dept.
from the really-big-number dept.
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!"
Related Stories
Submission: Ten-million-digit prime discovered? by Anonymous Coward
[+]
45th and 46th Mersenne Primes Confirmed 47 comments
kahunak writes to alert us that GIMPS has announced that the 45th and 46th Mersenne primes have been confirmed. The EFF's $100,000 award, for the first prime over 10 million digits in length, will probably be claimed. (We discussed no. 45 when it was announced.)
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
Link to wikipedia would be nice (Score:5, Informative)
http://en.wikipedia.org/wiki/Mersenne_prime [wikipedia.org]
Fun.
10 million digits (Score:5, Funny)
And you only get 6 digits in prize money? What a rip off. That is only one $digit per 1.67 million prime digits.
Re:10 million digits (Score:5, Funny)
You say that, but at some point someone told me that 1 is a prime number and 2 is as well, so therefore, prime numbers can be one prime number plus 1. Plus, I'm a biologist.
Parent
GPU's? (Score:5, Interesting)
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?
Re:GPU's? (Score:5, Interesting)
The Lucas-Lehmer test for Mersenne primes consists of repeated multiplication (modulo a fixed large number). Large-integer multiplication is done via floating-point FFT, which is nothing but massive amounts of operations on small numbers. I don't know how FFT implementations for GPUs compare, but intuitively I think they ought to be at least as fast as for CPUs. The primes tested by GIMPS are small enough to fit entirely in GPU memory, so latency doesn't seem like a problem.
(I don't really know much about any of this, so feel free to correct/enlighten me.)
Parent
Re:GPU's? (Score:5, Informative)
The weighted FFT algorithm used by GIMPS is called the Irrational Base Discrete Weighted Transform (IBDWT), and it was designed with Mersenne numbers in mind.
You're almost right about GPUs getting enough memory to start tackling this sort of problem, but the issue isn't memory, it's floating point precision.
The FFTs being done by GIMPS are fairly large, and the overall error introduced by the FFT operations is roughly proportional to the log of the size of the dataset. So as the numbers become larger and larger, less and less data can be stored within each of the floating-point values. Which leads to larger transforms, which leads to less data that can be stored, etc. It's a vicious circle.
In the case of a 10 million-digit prime, the worst-case scenario ends up with 1 bit of the original value per float, and a transform size of about 2 ** 25. The values themselves will take up about 128 megs of video memory.
(Side note: the most efficient FFT algorithms involve a "scratch" buffer that stores intermediate results-- so for a 128-meg data set, we would really need to have at least 256 megs of usable space on the video card.)
In this case, if we have floating-point values with only 23 bits of mantissa (as is the case with most graphics cards), we would have to be sure that no more than 22 bits of error could creep in over the course of the calculations. But given the size of the transforms, that's not very likely. In reality, we're likely to lose the results to rounding errors.
The only real way out of this problem is to use higher-precision numbers. Some graphics cards offer 64-bit floats, but they come with a huge performance hit. There are also some techniques for "emulating" higher precision on a graphics card, but they're pretty application-specific, and I don't know that they'd work for FFTs.
So, yeah-- the long and the short of it is that graphics cards just don't have the required precision for large-integer multiplication at the size GIMPS is doing. Smaller numbers are okay (in fact, I've written code that uses GPUs to accelerate large-integer multiplication-- there IS a speedup), but 10 million digits just isn't possible yet.
Hope that clears things up!
Parent
Just start at infinity... (Score:5, Funny)
And work backwards, that will find the largest much faster than starting at zero.
Prediction (Score:5, Funny)
I predict that the last digit will be... (Score:5, Funny)
...even!
Re:I predict that the last digit will be... (Score:5, Funny)
...even!
Well, I guess you've got a 50% chance...
Parent
Re:I predict that the last digit will be... (Score:5, Funny)
...even!
Well, I guess you've got a 50% chance*...
*For very small quantities of 50%
Parent
More information please (Score:5, Funny)
The submitter or editor could have at least typed the number into the summary. Lazy bastards.
Re:More information please (Score:5, Funny)
They didn't because it turns out the number is 7. The math
crowd are really embarrassed that they missed it when they
were checking the first time.
"Look, no one searches for Mersenne Primes down there, because
we all know they've been found. That someone made a typo and
left out 7 went undiscovered for years. We don't like to talk
about it."
Parent
Re:More information please (Score:5, Funny)
The number might have been too long. But they could have put the prime factorization in the summary.
Parent
Re:Forgive my ignorance (Score:5, Funny)
To what use will this long, long prime be put?
Absolutely none whatsoever. That's the beauty of mathematics.
Parent
Re:Forgive my ignorance (Score:5, Informative)
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.
Parent
Re:Forgive my ignorance (Score:5, Insightful)
Parent
Re:Forgive my ignorance (Score:5, Insightful)
"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.
Parent
Re:Forgive my ignorance (Score:5, Funny)
"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.
Parent
Re:Forgive my ignorance (Score:5, Funny)
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."
Parent
Re:Forgive my ignorance (Score:5, Funny)
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
Parent
Re:Forgive my ignorance (Score:5, Funny)
Consultants on the other hand can provide expensive proof that there are solutions, while being unable to provide one.
Parent
Re:Forgive my ignorance (Score:5, Informative)
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.
Parent
Re:What would really be neat... (Score:5, Insightful)
That is kinda less interesting because it depends on the system used to represent the number (binary, decimal, etc.) rather than an intrinsic property of the number
Parent
Perfect numbers and Mersenne Primes (Score:5, Interesting)
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
Parent
Re:Forgive my ignorance (Score:5, Funny)
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.
Parent
Re:Forgive my ignorance (Score:5, Insightful)
I guess some of us have different standards on beauty...
Parent
Re:Forgive my ignorance (Score:5, Funny)
Close, but she's only pretty useless.
Parent
Re:Forgive my ignorance (Score:5, Funny)
Parent
Re:Forgive my ignorance (Score:5, Funny)
Oblg.
http://xkcd.com/435/ [xkcd.com]
Parent
Re:Forgive my ignorance (Score:5, Funny)
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.
Parent
Re:Forgive my ignorance (Score:5, Insightful)
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.
Parent
Mod parent up (Score:5, Insightful)
Parent
Re:Forgive my ignorance (Score:5, Interesting)
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.
Parent
Re:Forgive my ignorance (Score:5, Informative)
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.
Parent
Re:Forgive my ignorance (Score:5, Informative)
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.
Parent
Re:Forgive my ignorance (Score:5, Insightful)
Parent
Re:Forgive my ignorance (Score:5, Funny)
...
(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?
Parent
Re:Forgive my ignorance (Score:5, Funny)
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.
Parent
Re:Forgive my ignorance (Score:5, Informative)
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).
Parent
Re:I dont understand why this is important (Score:5, Funny)
...he asks on slashdot.
Parent
Re:I dont understand why this is important (Score:5, Funny)
Parent
Because (Score:5, Insightful)
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.
Parent
Re:I dont understand why this is important (Score:5, Funny)
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.
Parent
Re:I dont understand why this is important (Score:5, Insightful)
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.
Parent
Re:Well, I just beat them! (Score:5, Informative)
You seem to misunderstand the meaning of prime [wikipedia.org]. 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.
Parent
Re:Well, I just beat them! (Score:5, Funny)
Depends. Is your day job working as a mathematician? :)
Parent
Re:I guess there's some room to ask... (Score:5, Informative)
FTFA:
Still, it's not hard to think of some more, well, "electronic frontier-ish" applications for that kind of money. The FPGA-based DES keysearch engine they built a few years back was cool. OTOH, this Mersenne prime business just sounds like they're paying for something that will become trivial soon enough anyway.
Parent
Re:Interesting (Score:5, Informative)
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.
Parent
Re:Moore-Otsuka-Helkenberg prime number sieve (Score:5, Informative)
"previously unknown"?
Uh, no. You have a very clunky Sieve of Eratosthenes. Digital roots isn't even a thing.
Also: numerological techniques would pertain to the spirituality of numbers and their mystic powers. Numeric techniques is what real computational mathematicians use.
Parent