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: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.
Comment removed (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.)
Re:so? (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]
Mersenne Primes Link (Score:2, Informative)
Re:I haven't tested this thoroughly, but... (Score:3, Informative)
(6*6) -1 = 35
Re:Sounds cool, but... (Score:1, Informative)
http://primes.utm.edu/notes/faq/why.html
"Why?" we are often asked, "why would anyone want to find a prime that big?"" I often now answer with "did you ever collect anything?"" or "did you ever try to win a competition?"" Much of the answer for why we collect large primes is the same as why we might collect other rare items. Below I will present a more complete answer divided into several parts.
Tradition!
For the by-products of the quest
People collect rare and beautiful items
For the glory!
To test the hardware
To learn more about their distribution
For the money?
This does not exhaust the list of reasons, for example some might be motivated by primary research or a need for publication. Many others just hate to see a good machine wasting cycles (sitting idle or running an inane screen saver).
Perhaps these arguments will not convince you. If not, just recall that the eye may not see what the ear hears, but that does not reduce the value of sound. There are always melodies beyond our grasp. (*)
1. Tradition!
Euclid may have been the first to define primality in his Elements approximately 300 BC. His goal was to characterize the even perfect numbers (numbers like 6 and 28 which are equal to the sum of their aliquot divisors: 6 = 1+2+3, 28=1+2+4+7+14). He realized that the even perfect numbers (no odd perfect numbers are known) are all closely related to the primes of the form 2p-1 for some prime p (now called Mersennes). So the quest for these jewels began near 300 BC.
Large primes (especially of this form) were then studied (in chronological order) by Cataldi, Descartes, Fermat, Mersenne, Frenicle, Leibniz, Euler, Landry, Lucas, Catalan, Sylvester, Cunningham, Pepin, Putnam and Lehmer (to name a few). How can we resist joining such an illustrious group?
Much of elementary number theory was developed while deciding how to handle large numbers, how to characterize their factors and discover those which are prime. (Look, for example, at the concepts required to develop simple proofs such as [1] or [2].) In short, the tradition of seeking large primes (especially the Mersennes) has been long and fruitful It is a tradition well worth continuing.
2. For the by-products of the quest
Being the first to put a man on the moon had great political value for the United States of America, but what was perhaps of the most lasting value to the society was the by-products of the race. By-products such as the new technologies and materials that were developed for the race that are now common everyday items, and the improvements to education's infrastructure that led many man and women into productive lives as scientists and engineers.
The same is true for the quest for record primes. In the tradition section above I listed some of the giants who were in the search (such as Euclid, Euler and Fermat). They left in their wake some of the greatest theorems of elementary number theory (such as Fermat''s little theorem and quadratic reciprocity).
More recently, the search has demanded new and faster ways of multiplying large integers. In 1968 Strassen discovered how to multiply quickly using Fast Fourier Transforms. He and Schönhage refined and published the method in 1971. GIMPS now uses an improved version of their algorithm developed by the long time Mersenne searcher Richard Crandall [see CF94].
The Mersenne search is also used by school teachers to involve their students in mathematical research, and perhaps to excite them into careers in science or engineering. And these are just a few of the by-products of the search.
3. People collect rare and beautiful items
Mersenne primes, which are usually the largest known primes, are both rare and beautiful. Since Euclid initiated the search for and study of Mersennes approximately 300 BC, very few have been found. Less than fifty in all of human history--that is rare!
But they are also beautiful. Mathematics, like all fields of study, has a definite notion of beauty. What qual
45th in order of discovery (Score:4, Informative)
Re:I haven't tested this thoroughly, but... (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: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:So what is it? (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:Actually the 47th (Score:2, Informative)
Re:so? (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 called engineering.
Re:Actually the 47th (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 2^n-1
Re:Actually the 47th (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:so? (Score:2, Informative)
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.