Slashdot Mirror
12M Digit Prime Number Sets Record, Nets $100,000
coondoggie writes "A 12-million-digit prime number, the largest such number ever discovered, has landed a voluntary math research group a $100,000 prize from the Electronic Frontier Foundation (EFF). The number, known as a Mersenne prime, is the 45th known Mersenne prime, written shorthand as 2 to the power of 43,112,609, minus 1 . A Mersenne number is a positive integer that is one less than a power of two, the group stated. The computing project called the Great Internet Mersenne Prime Search (GIMPS) made the discovery on a computer at the University of California, Los Angeles (UCLA) Mathematics Department."
The number known as a Mersenne prime, is the 45th known Mersenne prime, written shorthand as 2 to the power of 43,112,609, minus 1
Wikipedia lists it as the 47th known prime.
My work here is dung.
Call me a n00b, but I'm unsure there are any ways to use this newfound information about prime numbers.
Next time good ol' (2^43,112,609 - 1) comes up in conversation, I'll make sure to impress everyone with my new knowledge, but other than that, I feel no smarter for having read this article.
The biggest prime number I know is 8675309. I'll have to tell Jenny about this new one.
The CB App. What's your 20?
(2^43,112,609 - 1)th post!
Great,everyone starts using the new largest known prime number in their private key! That's like SUPER secure!
Glad to hear they're putting all those donations to use. There's no telling the impact on civil liberties that having access to a really large prime number will have...
Er, yeah no shit...I'm all for supporting the EFF(seriously, I am), but when I have to whip out my "what-the-fuck-good-is-THAT-for?!?" card, I tend to re-think my tax write-offs, especially to the tune of $100K...
One of EFFs goals is personal privacy. Encryption is based on prime numbers, the larger the prime, the more secure it is. Having an insanely large prime would take nearly forever to crack the encrypted message. http://www.cpaadvisor.us/sub/8_encryption.htm
The money does not come from regular donations.
http://www.eff.org/awards/coop
(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.)
Yes, in fact, it is very secure.
The fact that the (very large) prime modulus is not secret, but rather public, is part of the design of many PK encryption systems, and therein lies their beauty, simplicity, and charm. If you are interested in learning more about it, here's a description of one very widely used system: http://en.wikipedia.org/wiki/Diffie-Hellman_key_exchange
http://primes.utm.edu/mersenne/
They just got advertising in every math/scientific magazine on the planet.
Mostly read my professionals that make decent money.
Sounds like a well spent 100K to me.
The Kruger Dunning explains most post on
34^2+1 = 17*89
Paul Grosfield - the quicker picker upper.
...is a freaking genius. I can't stop laughing. I tip my hat to you, good sir/ma'am.
"I'd just like to emphasise that taking a million years isn't a metaphor here..." -Rich Bradshaw
(6*6) -1 = 35
It pays to be obvious, especially if you have a reputation for being subtle.
I can run PGP and have it generate primes for me within a few seconds that are sufficient for decent encryption, and they don't need to be a gazillion digits long.
I agree with you entirely. The debate, however, is in the definitions of "sufficient" and "decent". For most needs, you need far fewer than a gazillion digits. For national security type stuff, a gazillion digits may be appropriate. For a math/crypto nerd, even a bazillion gazillion digits will never be enough.
He's getting rather old, but he's a good mouse.
They could have made the reward $100,003 instead...
But anyone with a CS degree at least should understand the basics of why big primes make good private keys
Indeed. Although it should be noted that Mersenne primes are sort of useless for this. If you know one of the factors is a Mersenne Prime then there are only 47 candidates.
Now that everyone knows this number, I have to change my luggage combination again. Thanks for nothing EFF!
Well, there's spam egg sausage and spam, that's not got much spam in it.
The article is correct by order of discovery- it was the 45th Mersenne prime to be discovered (on August 23, 2008.) Two smaller Mersenne primes were discovered later, on September 6, 2008 and April 12, 2009, which are also included in the Wikipedia table.
Nope.
17*89 = 1513
34^2+1 = 1157
You are 50% correct, however, as you probably meant to type 13*89, which would work.
I think $100,000 is roughly how much, in electricity costs, it costs to run the many, many computers for 5-10 years needed to grind out this particular number. Plus maintenance and taxes. You could pretty much say this research was done "at cost".
moox. for a new generation.
Strictly speaking, large primes are useful but not specific large primes. Indeed, this Mersenne prime is much too large to be useful for practical cryptography.
The main reason that primes are useful for cryptography is that there are functions associated with primes where the functions are easy to calculate but have inverses that are very difficult to calculate unless one has extra information. The classic example of this is the discrete log problem. Essentially, if one is doing modular arithmetic with a given prime (that is arithmetic where you only look at the remainders when divided by that prime. This is essentially like a clock with p numbers on it. On a normal clock is arithmetic mod 12) then it turns out that for any prime p, there is a number k such that k^1, k^2, k^3... k^(p-1) taken mod pruns through all the possible remainders 1,2,3... p-1 (obviously not in order). Such a k is called a primitive root (or a generator) Now, it is very easy given a k and an n to calculate k^n (mod p). However, given the equation k^x=m (mod p) it is very hard to find the right value of x without doing a lot of work (essentially, you have to more or less list out k^1,k^2,k^3... until you get to m). The difficulty in this process is used in a number of public key crypto systems and other systems. For example, the Diffie-Hellman algorithm which was the first modern crypto algorithm discovered uses the difficulty of this process to make it so that two people can without ever having talked to each other before have a conversation and at the end of it have a secret code that no one else can figure out without impractical levels of computation. This is true even if one has access to all the communication that goes on between the two parties. The RSA algorithm which is more practical than DH for a variety of reasons also works off of a similar procedure.
The above is assuming that the discrete log is actually a difficult problem which everyone believes but is not proven. Proving this would imply that P != NP which is one of the Clay Millennium Problems (so million dollar prize and all that fun stuff). Mersenne primes are very interesting but not for any crypto related reason.
There is a link in TFA to the number. It gives an abbreviated version first, but links to the full number as well:
http://prime.isthe.com/chongo/tech/math/prime/m42643801/prime-c.html
The project GIMPS that is mentioned in the title uses a distributed computing system to search for Mersenne primes. They use a modified form of the Lucas-Lehmer test http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test where they use a Fast Fourier Transform to be able to do the large multiplications efficiently.
We care about Mersenne primes because they correspond to even perfect numbers. If one has a Mersenne prime 2^p -1 then (2^p-1)(2^(p-1)) is an even perfect number. This was proven by the ancient Greeks. Euler then proved much later that every even perfect number is of this form. The oldest two unsolved problems in mathematics are whether there are infinitely many even perfect numbers and whether there are any odd perfect numbers. Thus, every time we discover a new Mersenne prime we get a new even perfect number. And if we can ever get enough insight to resolve whether or not there are infinitely many Mersenne primes then we can resolve one of the oldest unsolved problems in all of mathematics.
"Voluntary" math research group? Is there any other kind?
I'm trying to imagine an "involuntary" math research group, and all I'm getting is scenes from dystopian science fiction ... or possibly a scene from the life of Léon Theremin.
-kgj
I was going by this description of RSA. Quote:
In real life situations the primes selected would be much larger, however in our example it would be relatively trivial to factor n, 3233, obtained from the freely available public key back to the primes p and q. Given e, also from the public key, we could then compute d and so acquire the private key.
I didn't go through all the math myself, but if this description is true, then knowing one of the primes makes factoring n becomes unnecessary, allowing us to "compute d and so acquire the private key."
So at least the RSA encryption is easily broken if you have a good guess as to one of the primes used.
Sure, but when you consider how often primes must be generated in this sort of algorithm, optimizations are very useful. (That's why most algorithms actually in use use parabolas in place of primes, generating random primes is too computationally intensive.) But research is always worthwhile to see if new approaches can be found (and often the research leads us down paths that most people would say "What can you do with that? Why the fascination with..."
If we knew it wouldn't be called research, it would be called engineering.
No, I wasn't kidding at all when I said "very secure". I really mean it. It's just that Kalirion (and you AC), and I are thinking of, and referring to, two very different systems of PK encryption, which have very different properties, and would be affected very differently by the choice of prime numbers.
In the case of Diffie-Hellman, only *one* prime number is used, and it is not a secret at all. It is transmitted in the clear, over an insecure channel, to the other party, in order to be used to establish the mutually shared secret key. This is by design, and in no way weakens the security of the encryption system. Please, don't take my word for it, just read the link in my first post.
In contrast, in the RSA system, which you and Kalirion are both referring to, *two* prime numbers are used, and these two primes must both be kept secret. Obviously, in this case, choosing one of the two secret primes from among the "famous" prime numbers, would certainly weaken the overall security of the encryption, by reducing the search space for a brute-force attack. However, given the huge set of primes from wich the other one could be chosen, I don't know whether choosing just one "famous" prime number for your secret pair would make the resulting secret key easy, or even computationally feasible to find, given our current state of technology.