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.
Re:Forgive my ignorance (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:Well, I just beat them! (Score:2, Informative)
2^x -1 is never prime if x is not prime. I do believe your number falls under that category.
Re:10 million digits (Score:3, Informative)
it could be the previous record holder plus one
No, it couldn't ;-).
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:Forgive my ignorance (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:GPU's? (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, this means the seemingly awesome power of the GPU is often reduced by orders of magnitude relative to an equivalent ops/sec rating on a CPU.
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:Well, I just beat them! (Score:4, Informative)
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:Forgive my ignorance (Score:4, Informative)
You forgot to divide by 8...bits != bytes
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.
Well go download it...most of it anyways (Score:2, Informative)
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.
Re:Forgive my ignorance (Score:1, Informative)
That has to be one of the best penis pill ad spoofs I've ever read. Kudos on that classy rewrite.
Not a troll
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: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:1, Informative)
No, he did it right. 33 million bits ~ 4 million bytes.
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: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 benchmarking check on it, its currently taking 26 days and a few hours to fully test exponents in the 42,000,000 range.
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!
Re:Forgive my ignorance (Score:3, Informative)
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:Forgive my ignorance (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:What would really be neat... (Score:5, Informative)
Can you prove that?
Sure. Every prime p has two digits in base p. QED.
Re:What would really be neat... (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: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 small).
I could represent the number twenty-six as 11 in the base, b that is the solution to
(1+1*b^1)=26 (in base ten), or:
25 = b
How about a slightly harder one? Twenty-six as 27:
(7+2*b^1)=26
b = 19/2
Hopefully you can see that I could pick pretty much anything.
Re:Forgive my ignorance (Score:1, Informative)