Become a fan of Slashdot on Facebook

typodupeerror

## 45th Known Mersenne Prime Found?396

Posted by samzenpus
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!"
This discussion has been archived. No new comments can be posted.

## 45th Known Mersenne Prime Found?

• #### Link to wikipedia would be nice (Score:5, Informative)

<qg@biodome.org> on Wednesday August 27, 2008 @07:22PM (#24773059) Homepage Journal
• #### Re:Forgive my ignorance (Score:2, Informative)

on Wednesday August 27, 2008 @07:28PM (#24773153)
When it comes to cryptography, when youbigger the prime numbers you have the harder it is to break the encryption.
• #### Re:Forgive my ignorance (Score:5, Informative)

<brain_recall@noSpAM.yahoo.com> on Wednesday August 27, 2008 @07:36PM (#24773227)
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), it becomes impractically large for cryptography.

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)

by Anonymous Coward on Wednesday August 27, 2008 @07:37PM (#24773237)

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)

on Wednesday August 27, 2008 @07:39PM (#24773253)

it could be the previous record holder plus one

No, it couldn't ;-).

• #### Re:Well, I just beat them! (Score:5, Informative)

on Wednesday August 27, 2008 @07:50PM (#24773357)

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)

<perry.matt54NO@SPAMyahoo.com> on Wednesday August 27, 2008 @07:51PM (#24773369)

To what use will this long, long prime be put?

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)

on Wednesday August 27, 2008 @07:52PM (#24773375)

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)

<tbrownaw@prjek.net> on Wednesday August 27, 2008 @07:52PM (#24773383) Homepage Journal

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)

on Wednesday August 27, 2008 @07:56PM (#24773439)
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.
• #### Re:I guess there's some room to ask... (Score:5, Informative)

on Wednesday August 27, 2008 @08:10PM (#24773585) Homepage Journal

FTFA:

(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.)

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)

by Anonymous Coward on Wednesday August 27, 2008 @08:16PM (#24773641)

You forgot to divide by 8...bits != bytes

• #### Re:Interesting (Score:5, Informative)

on Wednesday August 27, 2008 @08:36PM (#24773815) Homepage

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.

on Wednesday August 27, 2008 @09:00PM (#24774013)
basically, they distribute the prize to contributors...currently \$50,000 would go to you [mersenne.org]
• #### Re:Moore-Otsuka-Helkenberg prime number sieve (Score:5, Informative)

on Wednesday August 27, 2008 @09:13PM (#24774121)

"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)

by Anonymous Coward on Wednesday August 27, 2008 @09:18PM (#24774153)

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)

<spam_hole@NOSPAm.shaw.ca> on Wednesday August 27, 2008 @09:25PM (#24774227) Homepage
Testing a single candidate Mersenne prime takes a month of straight computation [mersenne.org] 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).
• #### Re:Forgive my ignorance (Score:5, Informative)

on Wednesday August 27, 2008 @10:09PM (#24774563)

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)

by Anonymous Coward on Wednesday August 27, 2008 @11:25PM (#24775091)

No, he did it right. 33 million bits ~ 4 million bytes.

• #### Re:Forgive my ignorance (Score:5, Informative)

on Wednesday August 27, 2008 @11:41PM (#24775181)

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)

on Thursday August 28, 2008 @12:03AM (#24775301)

>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)

by Anonymous Coward on Thursday August 28, 2008 @12:57AM (#24775571)

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)

on Thursday August 28, 2008 @03:18AM (#24776301) Homepage
No, that would be Max Planck [wikipedia.org].
• #### Re:What would really be neat... (Score:5, Informative)

on Thursday August 28, 2008 @03:34AM (#24776373)

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)

on Thursday August 28, 2008 @05:47AM (#24776971)

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)

on Thursday August 28, 2008 @06:56AM (#24777333)

Can you prove that?

Sure. Every prime p has two digits in base p. QED.

• #### Re:What would really be neat... (Score:3, Informative)

on Thursday August 28, 2008 @07:02AM (#24777377)

Every prime number has a prime number of digits in some base.

Can you prove that?

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)

<rustyp.freeshell@org> on Thursday August 28, 2008 @08:40AM (#24778447) Homepage Journal

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)

by Anonymous Coward on Thursday August 28, 2008 @01:19PM (#24782591)