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?
Since you're AC, I'll just send you here.
(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...
Encryption.
Go green: turn off your refrigerator.
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
(wikipedia)
Several public-key cryptography algorithms, such as RSA or the Diffie-Hellman key exchange are based on large prime numbers (for example with 512 bits). They rely on the fact that it is thought to be much easier (i.e., more efficient) to perform the multiplication of two (large) numbers x and y than to calculate x and y (assumed coprime) if only the product xy is known.
Many mathematical research subjects are not firmly grounded in real-world applications.
I have a basic understanding of the principle, but I'm still not seeing the practical application of constantly finding larger and larger prime numbers. Sure, a million-digit prime number is cool if math is your thing, but as best I can tell it's not useful in a practical sense. (Maybe it has some academic value that I'm not aware of, entirely possible.)
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 could be way off on this, but that's just how it seems to me.
Take any base 10 number that ends with 4 or 6. Square it. Add 1. So far, in my limited testing experience, it has worked.
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
What is it about Mersenne Primes that makes finding a new one worth $100k? Is there an intrinsic value to the number or is it just one of those things that are so hard to do, like running a world's record hundred meters, that the effort and talent to do it merits a rewarded?
...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
Ok, that's better.
Today, yes. It remains to be seen if, in 15 years time, we will be able to trivially decrypt your decent encryption. Finding good ways of generating larger primes is very important until Moore's law is proven dead.
Mersennes are useful for this as someone noted above.
... and this new founded information is coming from an organization going by the name of GIMPS?
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.
http://www.jcu.edu/math/vignettes/mersenne.htm
intellectual property law is philosophically incoherent. it is your moral duty to ignore it or sabotage it
You mean the 4th one? Optimus did die for real in the first movie (animated, back in the mid-80's), and was replaced by Rodimus Prime at the end of the movie. I'll admit I haven't seen most of the cartoons since then, so I'm not really sure where Mersenne came from.
-Space for rent
mersenne prime discoveries have a direct, practical use in cryptography. cryptography is very important for secure communication on teh intarwebs. secure communication outside the prying eyes of intrusive governments is very important for the eff and its goals
intellectual property law is philosophically incoherent. it is your moral duty to ignore it or sabotage it
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.
duh... to win $100,000 of course!
Walk with Music;
What is the awesome number? The summary makes a big deal about this number but doesn't include it! WtF?
Utilizing the synergization of benchmark e-solutions to pre-workaround action items!
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.
I don't know why they are running a story about something that happened August 2008!
http://science.slashdot.org/story/08/09/13/1940218/45th-and-46th-Mersenne-Primes-Confirmed
And since then we've found 2 more hence the 47th prime.
http://science.slashdot.org/story/09/06/13/2218226/47th-Mersenne-Prime-Confirmed
That's amazing. I've got the same combination on my luggage!
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.
Awesome...
--- Jon
I thought about that, but then the question arises: if in 15 years, we have the processing power to easily crack whatever I encrypted today... then in 15 years shouldn't we also have enough processing power to easily generate these primes Of This Magnitude?
From TFA:
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).
I'd hate to learn that EFF is using slave labor.
But, I wanted socialized health insurance!
A Mersenne number is a positive integer that is one less than a power of two, the group stated.
Yeah, well, you know, that's just, like, their opinion, man.
"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.
If you're Bill Gates, you can try to factor them.
But, I wanted socialized health insurance!
Your point is valid, and you're not the only one who thought of it. Others have pointed out that this didn't come from regular donations, but I just wanted to weigh in and say that the moderation you've received (currently "Score: 0, Troll") is ridiculous. Yours was a valid comment, and a useful contribution to this discussion.
"You cannot simultaneously prevent and prepare for war." -- Albert Einstein
What practical application does discovering gaseous planets that are >100 million light years away? It doesn't need a practical application to be interesting. Welcome to humanity, dipshit.
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.
Using a Mersenne prime for your private key is kinda like hiding the key to your house under the welcome mat. WAY too hard for any average dumb burglar to figure out.
Well, yeah, I kinda overlooked that (hoping for +1 Funny, karma-whore that I am).
-kgj
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.
I'm not convinced using one of the 48 known Mersenne primes as the basis for a new encryption algorithm is going to be particularly secure!
Well, sure. I was shooting for droll irony -- must've aimed low.
-kgj
I'm going to have to do a little research on this issue, to find out why the *EFF* funded this prize. As an EFF donor, I donate money to them so that they can use it to advance the causes of liberty and privacy. I'm a little puzzled at how them spending $100k of (I presume) *donor money* is advancing the cause of liberty or privacy? Here I thought my money was going to precedent-setting lawsuits and criminal trials, and to lobby congress and educate the press about technology and liberty/privacy issues?
I suppose *maybe* this is somehow tied into the last part (government/public education about the issues) sort of "crypto awareness", since most cryptography is based on large prime numbers, but I'm a bit skeptical at them moment that my donations are being used wisely.
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.
The Mersenne primes are useless for this task, though. They are so long and so far in between that you can guess which of them are involved by just looking at the length of any given key. Which would be _way_ too long to handle, anyway. And they could just use ECC instead.
So no, I am not sure that is the reason. In fact, I am sure that can't be the reason.
That being said, if anyone has any ideas, please share them :)
If you read the wikipedia article.. "It is not known whether any undiscovered Mersenne primes exist between the 39th (M13,466,917) and the 47th (M43,112,609) on this chart; the ranking is therefore provisional. Primes have also not been discovered in increasing order. For example, the 29th Mersenne prime was discovered after the 30th and the 31st. Similarly, the current record holder was followed by 2 smaller Mersenne primes, first 2 weeks later and then 8 months later."
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.
With the RSA system, knowing one prime number lets you find the other one by a single division operation, since the product of the two primes is public. But yes, the Diffie-Hellman encryption would stay secure since the prime is known already.
and would be affected very differently by the choice of prime numbers.
I think they're more affected by the rules for the process by which the primes are chosen... rather than the particular choice of primes.
Let p be the number from the summary. If your rule is "choose a random element of {p}", it's fine for D-H and ElGamal, bad for RSA. If it's "choose a random element of {primes less than or equal to p}" and you just happen to (randomly!) choose p, it's not a problem for RSA any more. It's not that p has any particular numeric properties that makes it weak (it might, but with RSA, these days I hear it's more important to choose large numbers rather than specific kinds of numbers).
Well, except that your adversary might try a dictionary attack against your secret primes.
It's the same with weak passwords: no particular password is weak, were it not for a lot of other people being more likely to choose it rather than "%xF8o0_a". And to all the people who choose bad passwords: choose some hunter2-ing better passwords! ;-)
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.
Note that this only works if all the evil people listening in don't modify anything that Alice and Bob. If they do, Alice knows that she's communicating in private with someone, not that she's communicating in private with Bob.
Here's how it works: the eavesdropper in the middle, Eve, pretends to be Alice as far as Bob can tell, and pretends to be Bob as far as Alice can tell. Alice and Eve can then communicate in private, as can Bob and Eve, so Eve can just pass along all the messages unmodified and listen in, or can insert, remove or alter messages.
Yes, I know that with RSA, if your adversary knows even one of your secret primes for certain, then she can compute your other secret prime, and therefore your secret key, in an instant, leaving you with no security at all. That's why I mentioned that they must both be kept secret.
The RSA situation that I was wondering about, and I'm still not sure about, is one where you have chosen just one famous prime for your secret pair, but your adversary doesn't know it for certain. In that case, I would expect the adversary to try famous primes first, when attempting to factor your key. But still they must test the primality of the other possible secret factor, that they derived by a single division. I wonder, would they find it truly feasible to do, or merely less difficult, because of your choice of one famous prime?
Yes, man-in-the-middle attacks still work. There are a number of other attacks that work also. This wasn't an attempt at explaining every single little detail of cryptography but rather answering the question which was asked- why we care about large primes for crypto purposes.
If dividing the product by one famous prime comes out to an easy integer but it takes a long time to test whether that integer is a prime, then you could just assume that it's a prime and see if you can derive the valid private key from that :)