12M Digit Prime Number Sets Record, Nets $100,000 232
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."
Actually the 47th (Score:5, Informative)
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 [wikipedia.org] the 47th known prime.
Re: (Score:2)
Re:Actually the 47th (Score:5, Funny)
It is the second largest prime: Both of all primes and Mersennes.
Wow, does that mean we're close to discovering the largest prime?
Re: (Score:2)
Yep, there' only one more left - just multiply all the ones we have and subtract 1. Err... and multiply all the ones we have and add 1. Crap, now there's more prime numbers to multiply.
Re: (Score:3, Informative)
This number itself has a lot of notable properties, besides generating another prime when plugged into the ol' 2-to-the-n-plus-1 thing...
Re: (Score:2)
Wow, does that mean we're close to discovering the largest prime?
Not close, just closer.
No matter how many primes we find, there are the same amount left over. Such is infinity.
45th in order of discovery (Score:4, Informative)
Re: (Score:2)
How did they miss 2?
Re: (Score:2)
Re: (Score:2)
computing friggen large numbers isn't as easy as it appears. Consider the fact that your computer contains a discrete(limited) number of bits, and the processor can operate on about 64 bits at a time (depending on architecture). Try putting 2^100 into a scientific calculator, it will probably overflow (can't represent a number that large). 2^43,112,609 is a huge, huge, number.
Re: (Score:2)
Re:Actually the 47th (Score:4, Informative)
Doesn't that make the 48th Mersenne prime 2 to the power of 43,112,610 minus 1? Can I have my $100,000 now please?
No, because not all Mersenne numbers are prime numbers. Example: 2 ^ 4 - 1 = 15 And 15 is divisible by both 3 and 5. It's highly unlikely for two Mersenne primes to be adjacent to each other as Mersenne numbers but not impossible. If you could verify your assertion, you might just be eligible. I'm guessing it's already been checked by no by GIMPS though.
Re:Actually the 47th (Score:5, Informative)
Here's the complete list of all consecutive Mersenne numbers that are both primes: 3 = 2^2-1 and 7 = 2^3-1.
2^n-1 can only be a prime if n is a prime, because 2^(ab) - 1 is divisible by 2^a - 1 and 2^b - 1. And (2, 3) are the only two consecutive primes.
Re: (Score:3, Funny)
Hmmmm.
Will knowing these numbers help me procreate before I die?
Re:Actually the 47th (Score:5, Funny)
Hmmmm.
Will knowing these numbers help me procreate before I die?
I don't know about the three or the seven, but the two certainly will... after all, it takes two to tango.
Re: (Score:2)
Folie a deux, menage a trois.
Re: (Score:3, Funny)
Re: (Score:2)
Yes, but only at your prime.
Re: (Score:2, Funny)
Re:Actually the 47th (Score:5, Funny)
Unfortunately, I'm afraid that knowing these numbers will prevent you from procreating before you die.
Re: (Score:2)
I have a question, if 2^n-1 can only be a prime if n is a prime... would using the new 12M digit prime in the article as n, result in a new bigger prime? can it be repeated?
Re: (Score:2, Informative)
Re: (Score:2)
2^n-1 can only be prime if n is prime. It doesn't mean that it must be prime if n is prime. For example, 11 is prime, but 2^11-1 = 2047, which is not prime (2047/23 = 89)
Re: (Score:2)
He said 2^n-1 can only be a prime if n is a prime. He didn't say the converse was true.
Yes, but asking if the converse is true is the first natural step after you prove something.
It can, however, be answered quickly by testing the first five primes, or by noting that there are a lot more than 47 primes between 2 and 43,112,609.
Re: (Score:2)
You have absolutely no idea what you're talking about.
Re: (Score:2, Informative)
If we simply focussed on running the existing primes through 2^n-1, we'd find every prine through a few billion didgits in a couple of years.
Unfortunately it's not that simple. Not all primes are of the form 2^n-1, and numbers of that form are not necessarily prime.
Currently there's no efficient algorithm for generating a list of primes in sequence and your estimate of a couple of years is way off (as in "many many lifetimes of the universe way off"). Even testing whether a number is prime is not efficient.
The reason work is concentrated on Mersenne primes is that there there is a particularly fast test for primality for numbers of the form
Re: (Score:2)
That is kind of a bad number to pick, because 4 isn't prime (2*2). And then go on to say that it is highly unlikely that 2 neighboring primes are mersenne primes when, the first 4 primes (2,3,5,7) are all mersenne primes, and then 13,17,19 are all in a row again.
Re: (Score:2)
It's still a mersenne number, which is his point. The parent AC up there first-replying to first-post also picked a bad non-prime number: eldavojohn's point.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
And it's easily proven:
If 2^x - 1 is prime, then neither 2^x - 1 nor 2^x is divisible by 3. Of any 3 consecutive integers, one must be divisible by 3. Therefore 2^x + 1 is divisible by 3.
Therefore 2*(2^x+1) = 2^(x+1) + 2 is divisible by 3, and so is 2^(x+1) - 1.
Re: (Score:2)
No. Mersenne primes are numbers which fit into the 2^n-1, but not every 2^n-1 is prime. Try, 2^4-1 = 15
Quite often though, when 2^n-1 is prime for the same n, 2^n+1 is also prime, but not always.
Re: (Score:2)
2^43112610-1 is definitely composite. 2^(2*m)-1 = (2^m-1)*(2^m+1)
So, 2^43112610-1 = (2^21556305-1)*(2^21556305+1)
Re: (Score:2)
It would have to be a very big abacus
Re: (Score:2)
Sounds cool, but... (Score:3, Insightful)
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.
Re:Sounds cool, but... (Score:5, Funny)
n00b
Re: (Score:3, Funny)
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.
You think you feel bad? Talk to the guy who just signed that $100,000 check for this...
Re: (Score:3, Interesting)
...who works for EFF.
So what's their interest in this? Is it cryptography related?
Re:Sounds cool, but... (Score:4, Informative)
Think about how easy it is for a computer to multiply together (2^43112609 - 1) and (2^13466917 - 1).
Then think about how long it would take a computer to identify the factors of the resulting number, given that it is composed of two primes with twelve and four million digits, respectively.
Cryptography is all about simple math operations that can be performed one way, but cannot be easily and quickly reversed without knowing a secret (in my example, one of the original primes).
Re: (Score:2)
It's not easy for a computer to multiply those two numbers! You would have to perform 2^56582998 multiplications (on a 64-bit processor) and as many additions... That would take pretty much literally forever.
Re: (Score:2)
Um... the primes in question are just a long list of ones.
Re: (Score:2)
So what's their interest in this?
That's what I was wondering, so I peeked [eff.org]. Initially when I saw this article, I was a bit disturbed, since people don't donate to the EFF for this purpose--that's what contributions to research organizations and universities are for. However, it turns out the money comes from a private individual specifically for this purpose; the EFF merely administers the award. It's free publicity for 'em in a good cause, a Good Thing by my reckoning.
Re: (Score:2)
It's a separate donation fund managed by the EFF. They're not stealing from our brave soldiers fighting the RIAA and the government.
Re: (Score:2)
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.
So as long as you know that water is wet, the sky is blue, and the Sun goes around the Earth you are content?
Man, oh, man... (Score:5, Funny)
Re: (Score:2)
Damn you Tommy Tutone!
Re: (Score:2)
What about 2 ^ 2079460347? You know, the odds that you can get rescued while floating in outer space by a passing Heart of Gold.
Re: (Score:2)
Re: (Score:2)
But the best prime "number" (encoded of course) is 5t34k.
I'm way late to this thread (Score:2, Funny)
(2^43,112,609 - 1)th post!
Mersenne Primes Link (Score:2, Informative)
A Question (Score:2)
Re: (Score:2)
The more digits that prime numbers have, the further apart adjacent primes are. If you imagine the value of a prime number represents the distance along a coastline in terms of centimeters, then you would only need a few billion to cover the entire length of a continent, and adjacent prime numbers would be separated by a few hundred metres.
These Mersenne prime numbers are hundreds of digits long, so as a distance that would be measured in light years, nor metres or kilometres. There just isn't the computati
Re: (Score:2)
The more digits that prime numbers have, the further apart adjacent primes are.
That's not actually true. As numbers get larger you'll get longer composite runs, but you'll still find prime constellations between some of those runs. If what you say was true, the twin prime conjecture would be closed with a "Myth: BUSTED!" sticker on it, instead of open with overwhelming evidence in its favor.
Re: (Score:2)
I think what he meant is that on average adjacent primes get further apart (see prime number theorem [wolfram.com]).
Re: (Score:2)
Re: (Score:3, Interesting)
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".
Whoever added the "founditontheground" tag... (Score:3, Insightful)
What a wasted opportunity (Score:5, Funny)
They could have made the reward $100,003 instead...
Re:What a wasted opportunity (Score:5, Funny)
They could have made the reward $100,003 instead...
yeah, brilliant idea. next day's headline would be "Five Mathematicians Slain in Argument Over Division of Prize Money"
Re: (Score:2)
They could have made the reward $100,003 instead...
yeah, brilliant idea. next day's headline would be "Five Mathematicians Slain in Argument Over Division of Prize Money"
Why? It's not like the prize is in Yen.
I'm pissed! (Score:4, Funny)
So what is it? (Score:2)
What is the awesome number? The summary makes a big deal about this number but doesn't include it! WtF?
Re: (Score:2, Informative)
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 [isthe.com]
Re: (Score:2)
I hope you were going for funny here, although I am curious as to how much RAM firefox would eat trying to display a page displaying a 12 million digit long string.
Re: (Score:2)
http://prime.isthe.com/no.index/chongo/merdigit/long-m42643801/prime-c.html [isthe.com]
Before: 140 MB used
Several minutes and 1 maxed CPU core later: Jumping between 250 MB and 300 MB used before I gave up and closed the tab.
Re: (Score:2)
i was.
Yeah, that would be h00t. Lemme see what happens to IE....
170MB. Wow.
Amazing coincidence (Score:2)
That's amazing. I've got the same combination on my luggage!
Various useful details (Score:4, Interesting)
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 [wikipedia.org] 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.
I'm glad it's voluntary (Score:2)
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.
Thank goodness it's voluntary (Score:5, Funny)
"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 [wikipedia.org].
Re: (Score:2)
My irony must be rusty (Score:2)
Ima Karma Whore (Score:2)
Re: (Score:2)
(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.
Re:so? (Score:4, Interesting)
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.
Re: (Score:2)
If you're Bill Gates, you can try to factor them.
Re:so? (Score:5, Funny)
Great,everyone starts using the new largest known prime number in their private key! That's like SUPER secure!
Re: (Score:3, Informative)
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 [wikipedia.org]
Re: (Score:3, Interesting)
I was going by this description of RSA [wikipedia.org]. 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 "com
Re: (Score:2)
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 digit
Re: (Score:3, Interesting)
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.
Re: (Score:2)
Re: (Score:2)
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?
Re: (Score:2, Informative)
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
Re: (Score:2, Interesting)
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.
Re: (Score:3, Insightful)
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...
Re: (Score:2)
Encryption.
Re:woo (Score:4, Insightful)
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.
Re: (Score:2, Informative)
Re:woo (Score:5, Informative)
The money does not come from regular donations.
http://www.eff.org/awards/coop [eff.org]
(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.)
Slashdot Mods: Grow Up (Score:2)
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.
Re: (Score:3, Interesting)
Re: (Score:2, Informative)
Nope.
17*89 = 1513
34^2+1 = 1157
You are 50% correct, however, as you probably meant to type 13*89, which would work.
Re: (Score:3, Informative)
(6*6) -1 = 35
Re: (Score:2)
bugger, - instead of +, I fail at maths
Re: (Score:2)
Euclid used that technique to show that there are an infinite number of primes, but it's not guaranteed to generate primes.
For example (2x3x5x7x11x13)+1 = 59x509
Re: (Score:2)
Then we just need to find *that* number...and it's reassuring that the problem is bounded.
(/facetious mode)
But the other hole in GGP's proposal is that the sequence "all known primes" has lots of gaps in it.
Re: (Score:2)
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.