×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

12M Digit Prime Number Sets Record, Nets $100,000

CmdrTaco posted more than 4 years ago | from the that's-a-lotta-bits dept.

Math 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."

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

232 comments

Actually the 47th (4, Informative)

eldavojohn (898314) | more than 4 years ago | (#29758193)

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

Anonymous Coward | more than 4 years ago | (#29758233)

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?

Re:Actually the 47th (3, Informative)

eldavojohn (898314) | more than 4 years ago | (#29758289)

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 (5, Informative)

gnasher719 (869701) | more than 4 years ago | (#29758397)

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.

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:Actually the 47th (2, Funny)

commodore64_love (1445365) | more than 4 years ago | (#29758765)

Hmmmm.

Will knowing these numbers help me procreate before I die?

Re:Actually the 47th (4, Funny)

tholomyes (610627) | more than 4 years ago | (#29758861)

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:Actually the 47th (4, Funny)

mcgrew (92797) | more than 4 years ago | (#29759507)

Unfortunately, I'm afraid that knowing these numbers will prevent you from procreating before you die.

Re:Actually the 47th (0)

Anonymous Coward | more than 4 years ago | (#29758291)

That one isn't prime.

Re:Actually the 47th (0)

Anonymous Coward | more than 4 years ago | (#29758293)

Unless of course it's not prime... you have to prove it first.

Re:Actually the 47th (-1, Troll)

Anonymous Coward | more than 4 years ago | (#29758641)

You know what news headline you will NEVER EVER see? "African scientist advances ANY FUCKING SCIENTIFIC FIELD with a new discovery!"

By the way, if a white guy who was born in South Africa moves to the USA and becomes a citizen... does he call himself an African-American?

Re:Actually the 47th (-1, Offtopic)

Anonymous Coward | more than 4 years ago | (#29758899)

Only if he wants a better chance of getting hired for a job via AA...

Re:Actually the 47th (1)

Neon Spiral Injector (21234) | more than 4 years ago | (#29758349)

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:Actually the 47th (1)

Ann Coulter (614889) | more than 4 years ago | (#29758437)

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:Actually the 47th (1)

Nadsat (652200) | more than 4 years ago | (#29758771)

It is the second largest prime: Both of all primes and Mersennes. It is not, as the summary states, the "largest such number ever discovered"

Re:Actually the 47th (1, Interesting)

Anonymous Coward | more than 4 years ago | (#29759021)

It's the 47th by size; 45th by order of discovery. Two smaller Mersenne primes were discovered after the current record-holder. One was discovered within a couple of days of the discovery of the prize-winner-- and it was, itself, large enough to claim the EFF prize ($100k for 10M digits).

45th in order of discovery (3, Informative)

Noren (605012) | more than 4 years ago | (#29759033)

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.

so? (0)

Anonymous Coward | more than 4 years ago | (#29758225)

What can you do with big primes? Why the fascination?

I've heard the "Oh, it's useful in crypto" answer, but never WHY it's useful in crypto.

Re:so? (0, Flamebait)

FlyingBishop (1293238) | more than 4 years ago | (#29758355)

What can you do with plutonium? I mean, I've heard, oh it's useful in nuclear bombs, but never WHY it's useful in nuclear bombs.

You haven't heard why because you're not a fucking cryptoanalyst.

Now, if you really want a primer on primes and cryptography http://en.wikipedia.org/wiki/RSA [wikipedia.org] is a good place to start. But anyone with a CS degree at least should understand the basics of why big primes make good private keys

Re:so? (5, Funny)

kalirion (728907) | more than 4 years ago | (#29758419)

Great,everyone starts using the new largest known prime number in their private key! That's like SUPER secure!

Re:so? (3, Informative)

maxfresh (1435479) | more than 4 years ago | (#29758611)

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 [wikipedia.org]

Re:so? (1)

Jeian (409916) | more than 4 years ago | (#29758557)

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.

Re:so? (1)

FlyingBishop (1293238) | more than 4 years ago | (#29758813)

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 [wikipedia.org] as someone noted above.

Re:so? (2, Interesting)

gnick (1211984) | more than 4 years ago | (#29758837)

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:so? (0)

Anonymous Coward | more than 4 years ago | (#29759195)

What use is a newborn child?

Re:so? (2, Interesting)

91degrees (207121) | more than 4 years ago | (#29758883)

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.

Re:so? (1)

Yold (473518) | more than 4 years ago | (#29758555)

(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? (3, Interesting)

JoshuaZ (1134087) | more than 4 years ago | (#29759439)

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.

waste of money (-1, Troll)

Anonymous Coward | more than 4 years ago | (#29758243)

isn't there anyone out there doing useful research we could fund with this money?

Re:waste of money (0)

Anonymous Coward | more than 4 years ago | (#29758261)

Cloud Computing?

Sounds cool, but... (2, Insightful)

GMonkeyLouie (1372035) | more than 4 years ago | (#29758267)

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... (-1, Troll)

Anonymous Coward | more than 4 years ago | (#29758391)

It enlarges all our penises you n00b!!

Re:Sounds cool, but... (2, Funny)

geekmux (1040042) | more than 4 years ago | (#29758503)

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:Sounds cool, but... (2, Interesting)

Nerdposeur (910128) | more than 4 years ago | (#29759035)

Talk to the guy who just signed that $100,000 check for this...

...who works for EFF.

So what's their interest in this? Is it cryptography related?

Re:Sounds cool, but... (4, Informative)

Anonymous Coward | more than 4 years ago | (#29759377)

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:Sounds cool, but... (1, Informative)

Anonymous Coward | more than 4 years ago | (#29758827)

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 qualities are perceived as beautiful in mathematics? We look for proofs that are short, concise, clear, and if possible that combine previous disparate concepts or teach you something new. Mersennes have one of the simplest possible forms for primes, 2n-1. The proof of their primality has an elegant simplicity. Mersennes are beautiful and have some surprising applications.

4. For the glory!

Why do athletes try to run faster than anyone else, jump higher, throw a javelin further? Is it because they use the skills of javelin throwing in their jobs? Not likely. More probably it is the desire to compete (and to win!)
This desire to compete is not always directed against other humans. Rock climbers may see a cliff as a challenge. Mountain climbers can not resist certain mountains.

Look at the incredible size of these giant primes! Those who found them are like the athletes in that they outran their competition. They are like the mountain climbers in that they have scaled to new heights. Their greatest contribution to mankind is not merely pragmatic, it is to the curiosity and spirit of man. If we lose the desire to do better, will we still be complete?

5. To test the hardware

(This one has historically been used as an argument to get the computer time, so it is often a motivation for the company rather than the individual)
Since the dawn of electronic computing, programs for finding primes have been used as a test of the hardware. For example, software routines from the GIMPS project were used by Intel to test Pentium II and Pentium Pro chips before they were shipped. So a great many of the readers of this page have directly benefited from the search for Mersennes.

Slowinski, who has help find more Mersennes than any other, works for Cray Research and they use his program as a hardware test. The infamous Pentium bug was found in a related effort as Thomas Nicely was calculating the twin prime constant.

Why are prime programs used this way? They are intensely CPU and bus bound. They are relatively short, give an easily checked answer (when run on a known prime they should output true after their billions of calculations). They can easily be run in the background while other "more important" tasks run, and they are usually easy to stop and restart.

6. To learn more about their distribution

Though mathematics is not an experimental science, we often look for examples to test conjectures (which we hope to then prove). As the number of examples increase, so does (in a sense) our understanding of the distribution. The prime number theorem was discovered by looking at tables of primes.

Simple calculations hare found patterns, such as the prime number races, which have led to significant amounts of research.

7. For the money?

There are a few who seek primes just for the money. There are prizes for the first prover ten-million digit prime ($100000), the first hundred-million digit prime ($150000), and the first billion digit prime ($250000).

Re:Sounds cool, but... (0)

Anonymous Coward | more than 4 years ago | (#29759203)

and the improvements to education's infrastructure that led many man and women into productive lives as scientists and engineers

Hahaha if the educational system was so improved then why are there so many dumbasses everywhere? That part about women being productive scientists and engineers was pretty funny too! Yeah, 1% of them can do it but only because they have masculine traits, the rest of the women just aren't interested and all the PC "inclusiveness" in the world won't make them want to do this kind of work and you know it.

they're useful for security researchers (1)

circletimessquare (444983) | more than 4 years ago | (#29758889)

http://www.jcu.edu/math/vignettes/mersenne.htm [jcu.edu]

Why So Much Interest in Primes?

You might wonder whether the search for large primes is of any value. Apart from the adventurous spirit of exploration, there actually are uses for large prime numbers. One of the most important applications is to the field of cryptography -- the encoding and decoding of messages. National security often relies on having a secure method of encoding and deciphering messages; yet the existence of high-speed computers have rendered all but the most sophisticated coding schemes insecure. One commonly used method of message coding is the RSA scheme, named for its creators, Ron Rivest, Adi Shamir, and Len Adleman. The RSA scheme relies on the fact that it is easy to multiply two prime numbers, yet hard to factor their product -- especially if the prime numbers are large. Consequently, knowledge of large prime numbers can lead to coding schemes that are difficult to break.

Re:Sounds cool, but... (1)

Duradin (1261418) | more than 4 years ago | (#29759317)

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?

Re:Sounds cool, but... (0)

Anonymous Coward | more than 4 years ago | (#29759553)

memorize 43112609 now and if you happen to travel back more than 30 but less than 50 years, people who have access to millions of dollars in computer equipment just might believe your story.

Woah. (-1, Troll)

Anonymous Coward | more than 4 years ago | (#29758269)

That's like OVER 9000!!!

Man, oh, man... (4, Funny)

bennomatic (691188) | more than 4 years ago | (#29758283)

The biggest prime number I know is 8675309. I'll have to tell Jenny about this new one.

Re:Man, oh, man... (0)

Anonymous Coward | more than 4 years ago | (#29758403)

Don't call her; you'll get this guy [gawker.com] instead.

Re:Man, oh, man... (1, Funny)

Anonymous Coward | more than 4 years ago | (#29758663)

the prime number 641 should be high enough for everybody

Re:Man, oh, man... (0, Redundant)

.sig (180877) | more than 4 years ago | (#29758759)

I'd rather have 655357, as anything more than 655360 (640K) is just too much.

Re:Man, oh, man... (1)

dkleinsc (563838) | more than 4 years ago | (#29759117)

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:Man, oh, man... (0)

Anonymous Coward | more than 4 years ago | (#29759625)

Jenny, I got your number, I need to make you prime.

woo (0, Troll)

nomadic (141991) | more than 4 years ago | (#29758329)

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

Re:woo (2, Insightful)

geekmux (1040042) | more than 4 years ago | (#29758451)

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:woo (3, Insightful)

geekoid (135745) | more than 4 years ago | (#29758651)

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.

dude (1)

circletimessquare (444983) | more than 4 years ago | (#29758973)

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

Re:woo (5, Informative)

Nibbler999 (1101055) | more than 4 years ago | (#29758599)

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:woo (0)

Anonymous Coward | more than 4 years ago | (#29759147)

Thanks, I was a bit miffed at this use of funds too.

I'm way late to this thread (2, Funny)

Anonymous Coward | more than 4 years ago | (#29758357)

(2^43,112,609 - 1)th post!

nice! (0)

Anonymous Coward | more than 4 years ago | (#29758387)

A prime example of what can be done when....gah *dodges tomatoes*

What?!? Somebody else found this number? (0)

Anonymous Coward | more than 4 years ago | (#29758533)

Now I'll gave to change my PIN number again. Just as well... I was getting a little tired typing it in every time anyway!

Obligatory (0)

Anonymous Coward | more than 4 years ago | (#29758585)

2 ^ 43112609 - 1? That's the same combination I have on my luggage!

I haven't tested this thoroughly, but... (1)

The Altruist (1448701) | more than 4 years ago | (#29758595)

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.

Re:I haven't tested this thoroughly, but... (2, Interesting)

mctk (840035) | more than 4 years ago | (#29758671)

34^2+1 = 17*89

Re:I haven't tested this thoroughly, but... (2, Informative)

Anonymous Coward | more than 4 years ago | (#29759125)

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:I haven't tested this thoroughly, but... (0)

Anonymous Coward | more than 4 years ago | (#29758745)

I have read many crazy ways people find primes. I must admit, the one you suggested is the craziest i have come across.

Re:I haven't tested this thoroughly, but... (0)

Anonymous Coward | more than 4 years ago | (#29758853)

Why go to all that trouble when you can just take all known primes, multiply them by each other, then add 1? Repeat as necessary until you achieve the desired size BFPN (Big Fricking Prime Number).

Re:I haven't tested this thoroughly, but... (1)

SoVeryTired (967875) | more than 4 years ago | (#29759127)

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:I haven't tested this thoroughly, but... (0)

Anonymous Coward | more than 4 years ago | (#29759551)

Or, simpler, 3x5 + 1 = 16 = 2x2x2x2...

Re:I haven't tested this thoroughly, but... (0)

Anonymous Coward | more than 4 years ago | (#29759589)

Correct. This proof just states that either your number is a prime or it is divisible by a prime larger than the largest prime in your multiplication (here both 59>13 and 509>13.)

A Question (1)

rshol (746340) | more than 4 years ago | (#29758661)

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?

Re:A Question (1)

mikael (484) | more than 4 years ago | (#29758823)

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 computational power to check every single possible location, so they use Mersenne prime numbers are a way of taking a short cut to known locations where a prime number might be located.

Re:A Question (1)

KevinKnSC (744603) | more than 4 years ago | (#29759311)

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:A Question (1)

Locke2005 (849178) | more than 4 years ago | (#29758941)

What is it about going to the Moon that makes it worth spending $20 billion? Advances in pure mathematics aren't done for immediate benefit, they are done on the off chance that the new "discovery" might be useful some day, like non-Euclidean geometry. In this case, it was more of an incentive to develop the algorithms and computing power necessary to deal effectively with the problem space. Hopefully this provided insights into how other large, intractable problems may be solved.

Re:A Question (2, Interesting)

Hadlock (143607) | more than 4 years ago | (#29759379)

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... (2, Insightful)

magsol (1406749) | more than 4 years ago | (#29758729)

...is a freaking genius. I can't stop laughing. I tip my hat to you, good sir/ma'am.

A new autobot discovered? (0)

Anonymous Coward | more than 4 years ago | (#29758805)

We'll definitely need Mersenne Prime when Optimus finally dies for real in the 3rd Transformers movie.

Re:A new autobot discovered? (1)

.sig (180877) | more than 4 years ago | (#29758901)

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.

Wait a minute... (1)

01100111 (797441) | more than 4 years ago | (#29758819)

... and this new founded information is coming from an organization going by the name of GIMPS?

What a wasted opportunity (5, Funny)

y5 (993724) | more than 4 years ago | (#29758863)

They could have made the reward $100,003 instead...

Re:What a wasted opportunity (5, Funny)

bitt3n (941736) | more than 4 years ago | (#29759153)

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"

So what is it? (1)

AP31R0N (723649) | more than 4 years ago | (#29759253)

What is the awesome number? The summary makes a big deal about this number but doesn't include it! WtF?

Amazing coincidence (1)

noidentity (188756) | more than 4 years ago | (#29759597)

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

That's amazing. I've got the same combination on my luggage!

Various useful details (3, Interesting)

JoshuaZ (1134087) | more than 4 years ago | (#29759687)

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.

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...