45th Known Mersenne Prime Found? 396
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!"
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: (Score:2)
Well now, as the summary points out, it could be less than 10 million digits. For instance, it could be the previous record holder plus one. My calculator only goes up to 8 digits, so I can't test it one way or another.
Re: (Score:3, Informative)
it could be the previous record holder plus one
No, it couldn't ;-).
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.
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: (Score:3, Informative)
GPU performance is geared towards floating point and massively parallel operations on small numbers. Unfortunately, neither of those characteristics are particularly handy for dealing with large primes.
Even in the general computing scenarios where they are useful, they are frequently wasting a lot of resources to accomplish the task. The Folding@Home team has noted that due to poor random access performance it is usually more efficient to recompute values than to retrieve them from memory. In practice, t
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.)
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!
ntt instead of fft? (Score:3, 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 a
Darn...... (Score:2)
I was hoping it would be me. I have been using ./mprime on all my boxes for years now.
Congrats to the team and world.
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...
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%
I guess there's some room to ask... (Score:2, Interesting)
... 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.
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.
Re: (Score:2)
Umm, that prize money was from a single donation that was made fir the precise purpose of funding this search. They are not using any other donations for this purpose. (I'm betting it was a half million dollar donation (or perhaps a full million dollar donation) made with the condition that part of it be reserved for this purpose. But the remainder of the donation would still be too large for the EFF to ignore.
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."
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.
Prime (Pulp) Fiction (Score:3, Funny)
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.
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.
Re: (Score:3, Funny)
So this is like math's version of Paris Hilton? Pretty but useless?
Re:Forgive my ignorance (Score:5, Funny)
Close, but she's only pretty useless.
Re: (Score:3, Funny)
Prime numbers routinely prove to be useful.
I, for one, will be using it for my hashtables, thank you very much.
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.
Re:Forgive my ignorance (Score:5, Funny)
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.
Re:Forgive my ignorance (Score:5, Insightful)
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.
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.
Re: (Score:3, Informative)
Re:Forgive my ignorance (Score:5, Funny)
Quantum Physics has many fathers. Classical physics is a bit of a slut.
Re:Forgive my ignorance (Score:5, Funny)
Put another way, mathematics is to physics, as masturbation is to sex.
What would really be neat... (Score:4, Funny)
...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.
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
Re: (Score:3, Insightful)
Re:What would really be neat... (Score:5, Informative)
His point was that while a number like 193 has a prime number of digits in decimal, if you change it to binary (11000001) it is no longer a prime number of digits long. So no, it is not an inherent property of the number. Every prime number has a prime number of digits in some base.
Re: (Score:3, Interesting)
But what if the base was also prime?
Ooh, ooh, what if the number of all the possible bases (less than the number itself) such that the number of digits of the representation of the prime number was also a prime number? How about all the number of prime bases?
Maths is fun, even if not always useful.
Re:What would really be neat... (Score:5, Informative)
Can you prove that?
Sure. Every prime p has two digits in base p. QED.
Re: (Score:3, Informative)
Trivially.
N in base N has the representation 10 which has two digits. 2 is prime. QED.
Any base greater than the square root of the number and smaller than or equal to the number will have two digits in its representation.
Tim.
Re:What would really be neat... (Score:4, Insightful)
Every prime number has a prime number of digits in some base.
Can you prove that?
Every prime, p, consists of p digits in unary [wikipedia.org].
Re: (Score:3, Informative)
So we've got two very simple proofs so far.
If you look at the definition of positional notation [wikipedia.org], there's not really anything in there that precludes the use of non-natural number bases (though by the Cancel Reply
Parent
Post Anotraditional definition, not all numbers can be represented in all bases).
The point is, though, that there is a mapping between almost every number and almost every representation (obviously, it must consist of more than one digit to work, and there may be no solution if the base is too
Re: (Score:3, Interesting)
The number of digits in a Mersenne prime is always a prime number, if it's written in base 2 ;)
Re:What would really be neat... (Score:4, Funny)
Re: (Score:3, Funny)
Re:What would really be neat... (Score:5, Funny)
I'm sure that would be odd if you found it.
Re:What would really be neat... (Score:4, Interesting)
You mean this?
2^2-1=3 (prime)
2^3-1=7 (prime)
2^7-1=127 (prime)
2^127-1=170141183460469231731687303715884105727 (prime)
2^170141183460469231731687303715884105727-1="universe overflow" (is it prime? doubtful!)
Re:What would really be neat... (Score:4, Insightful)
1^2-1 = 0, not one! Besides, 1 is not a prime number, by definition.
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
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."
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
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.
Re:Forgive my ignorance (Score:5, Interesting)
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
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.
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.
Re:Forgive my ignorance (Score:4, Funny)
Must.... resist... mother joke...
Re:Forgive my ignorance (Score:5, Insightful)
I guess some of us have different standards on beauty...
Re: (Score:3, Informative)
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.
Re: (Score:2, Informative)
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.
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.
Re:Forgive my ignorance (Score:4, Informative)
You forgot to divide by 8...bits != bytes
Re:Forgive my ignorance (Score:5, Insightful)
right (Score:2, Funny)
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.
Re: (Score:3, Interesting)
Re: (Score:2)
Re: (Score:3, Informative)
That depends. If it's over 10,000,000 digits then it will be cashed in for $100,000 [eff.org].
Re: (Score:2)
Re: (Score:3, Insightful)
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.
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).
Re: (Score:3, Informative)
>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 benchm
Re: (Score:2, Funny)
>> 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?
Re:Forgive my ignorance (Score:5, Funny)
Re:Forgive my ignorance (Score:5, Funny)
Oblg.
http://xkcd.com/435/ [xkcd.com]
Re:Forgive my ignorance (Score:4, Funny)
You're complaining?
I studied psychology!
:(
Re: (Score:3, Funny)
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.
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.
Mod parent up (Score:5, Insightful)
Re: (Score:3, Insightful)
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.
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.
Re:Forgive my ignorance (Score:4, Funny)
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?
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.
Re: (Score:3, Funny)
"Is that a Mersenne prime in your pocket or are you just happy to see me?"
Re:I dont understand why this is important (Score:5, Funny)
...he asks on slashdot.
Re:I dont understand why this is important (Score:5, Funny)
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.
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.
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.
Re: (Score:3, Insightful)
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 d
Re: (Score:2, Informative)
2^x -1 is never prime if x is not prime. I do believe your number falls under that category.
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.
Re:Well, I just beat them! (Score:5, Funny)
Depends. Is your day job working as a mathematician? :)
Re:Well, I just beat them! (Score:4, Informative)
Re: (Score:2)
I think that's why he bold-ed the last digit
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.
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.