## 42nd Mersenne Prime Probably Discovered 369

RTKfan writes

*"Chalk up another achievement for distributed computing! MathWorld is reporting that the 42nd, and now-largest, Mersenne Prime has probably been discovered. The number in question is currently being double-checked by George Woltman, organizer of GIMPS (the Great Internet Mersenne Prime Search). If this pans out, GIMPS will have been responsible for the eight current largest Mersenne Primes ever discovered."*
## Uses? (Score:3, Interesting)

Encrypting?

## Re:Uses? (Score:5, Funny)

## Re:Uses? (Score:5, Funny)

Chics dig it.Either that or their eyes glaze over and you sneak a quick peck before they slap you silly.

"ah, l'amour"## Re:Uses? (Score:5, Funny)

## Re:Uses? (Score:4, Funny)

## Re:Uses? (Score:2)

## Re:Uses? (Score:3, Funny)

Wait, I mean just the 42th Mersene prime

## Re:Uses? (Score:5, Funny)

The theory is that there is an infinite number of these numbers, but they are unlikely to prove the theory by finding them all...

## Re:Uses? (Score:2)

There are an infinite number of numbers hence an infinite number of infinite primes from that set of infinite numbers.

The nice thing was that it only took a billionth of second to figure it all out.

## Re:Uses? (Score:3, Insightful)

## Overheard in the Math Dept... (Score:4, Funny)

## Re:Uses? (Score:4, Informative)

## Re:Uses? (Score:3, Insightful)

1) The number in question really is prime, as you suggested

2) The number in question isn't prime. Then it has prime divisors, none of them in your list (because none of the primes in the list divided our new number).

In both cases, we have derived a way to find at least one new prime fr

## Re:Uses? (Score:4, Informative)

## Re:Uses? (Score:4, Informative)

Actually, this theory has already been proven [mathforum.org].IMNSHO, but that was

theworst proof of infinite number of primes. Why introduce unique factorizability when you don't need to? Why introduce something foreign that you are not going to prove when there is absolutely no need for it?The most elegant proof I've seen so far (but I don't know any website showing it, so I can't link to it) is this: For any given N, an integer, consider N!+1, which is greater than N (where N! is defined by N! = 1 * 2 * 3 * ... * N). If this number is divisible by no other number than 1 and N!+1, then we are done (i.e. we have proven that given any arbitrary integer, there is a prime greater than tat integer). If this number is divisible by a prime, than that prime can't be less than or equal to N, since any integer (not equal to 1) less than or equal to N divides N! (see the definition of N!) but does not divide 1. Therefore, the prime that divides N! is greater than N. QED.

This proof involves no assumption (additional to assumptions (i.e. axioms) of the set of integers) other than this (which also happens to be much easier to prove than factorizability into primes): if n divides a + b and n divides a, then n divides b as well.

## Re:Uses? (Score:4, Informative)

And, no, one does not encrypt with Mersenne primes. The rarity of such numbers makes a "brute force" crypto-analysis seem rather plausible. Best to use an ordinary prime number-- there are, after all, many more of them to choose from.

## Re:Uses? (Score:2)

Using a mersenne prime for the public exponent is no problem though. Both 3 and 7 are used quite a lot for this purpose, though 65537 is used most (and this is not a mersenne prime).

## Re:Uses? (Score:3, Insightful)

Encryption discussions have to take place in a "computing" domain, where a prime only exists if it has been computed to be prime by at least one computer somewhere in the world, and where the prime number can fit on a distribution medium.

Arguing that there are as many Mersenne primes as regular primes is only possible in a theoretical domain in which countably infinite sets can be said to exist.

## Re:Uses? (Score:2)

There ara probably as many Mersenne primes as regular primes. Thus you could just as well encrypt with Mersenne primes.Not really. Since there are so few known Mersenne primes, the problem of factoring n to find the prime factors p and q to calculate phi(n) in order to crack RSA for example is greatly simplified if either p or q is a Mersenne prime. Perform 42 divisions and you're done.

## GOOD QUESTION! (Score:2)

If an expert gets excited, there's usually a reason. It's reasonable for non experts to ask what that reason is.

TW

## Re:GOOD QUESTION! (Score:4, Informative)

In all seriousness, they are interesting mainly because they are so simple mathematically that very very early mathematicians got interested in them. But even after hundreds of years of interest among mathematicians, there's no formula for predicting them, and very little successfully proven about them.

Since they are so rare, each find is a significant advancement for those who might be interested in trying to find a pattern.

## Re:GOOD QUESTION! (Score:3, Informative)

There may or may not be patterns in the way Merseinne primes occur.

If there are any patterns in Merseinnes, we may need to find more examples than we had before we can find those patterns.

If we do find patterns, they may or may not help us find other patterns that apply to other types of large primes in more general ways.

There is no guarenteed use outside of abstract math, but there is at least a small possibility we could crack one of the really big problems in crypto

## Re:Uses? (Score:3, Informative)

In Computational Complexity's terms, we like to design "efficient" algorithms.

One of the criteria used to say if an algorithm is efficient or not is to measure the time it takes to execute in terms of the size of its input.

We are usually concerned with designing faster algorithms (especially when we have to deal with huge inputs --- that's one of the things that people have in min

## Re:Uses? (Score:2)

Heh... how did this get modded informative? It's no use at all for encryption. Maybe 'funny' would be a better moderation...

## Re:Uses? (Score:5, Insightful)

## Re:Uses? (Score:2)

## Re:Uses? (Score:2)

42is not a good choice, since it's too obvious.## Of course... (Score:5, Funny)

## Re:Of course... (Score:4, Funny)

## Dont you mean.. (Score:2)

## Sheesh (Score:2, Funny)

The number in question is currently being double-checked by George Woltman, organizer of GIMPSAnd while George takes time off to double-check Mersenne primes, GIMP doesn't get any closer to the usability of Photoshop...

## Practical Applications/Uses? (Score:5, Insightful)

## Re:Practical Applications/Uses? (Score:2, Informative)

## Re:Practical Applications/Uses? (Score:4, Informative)

From here [haugk.co.uk]:

Finding new Mersenne primes is not likely to be of any immediate practical value. This search is primarily a recreational pursuit. However, the search for Mersenne primes has proved useful in development of new algorithms, testing computer hardware, and interesting young students in math.## Re:Practical Applications/Uses? (Score:5, Informative)

Also, necessity is the mother of invention. Even if Big Primes aren't really a necessity, it has brought forth some really innovative algorithms and methods to finding prime numbers. Furthermore, it has developed newer and faster ways for multiplying integers.

In 1968, Strassen figured out how to multiply integers quickly by using Fast Fourier Transforms. Strassen, along with Schönhage improved on the method and published a refined version in 1971. GIMPS now uses an improved version of their algorithm. This improved version was developed by Richard Crandall (a longtime researcher of Mersenne Primes).

Another application of finding Prime Numbers is to test computer hardware. Since testing Primes involves a thorough excercise of basic mathematical operations, it provides a good test for hardware. Software routines from GIMPS were used by Intel to test the PII and the Pentium Pro chips before they were shipped. The search for prime numbers was also indirectly responsible for the discovery of the infamous FDIV bug on the Pentium, during the calculation of the twin prime constant (by Thomas Nicely).

## Re:Practical Applications/Uses? (Score:4, Funny)

## Re:Practical Applications/Uses? (Score:4, Insightful)

## Re:Practical Applications/Uses? (Score:3, Interesting)

Whatever the case, this must be a more useful application for CPU power than Seti@home, which is a total waste of energy. Literally.

What we need are more projects that use distributed computing for useful calculations that could further science or solve problems. Universities build giant supercomputers to help their students calculate equations and solve problems. Maybe th

## Re:Practical Applications/Uses? (Score:4, Insightful)

Can someone explain what the application/use these primes are for?Communicating with alien species, perhaps.

Mersenne primes have two interesting properties that might catch the attention of alien species: when written in binary, they are entirely composed of '1' bits; and, of course, they are prime.

A sure way to prove to another being that you are intelligent is to spew a bunch of numbers which all happen to be prime. The fact that they can be tranmitted using only '1' bits means the modulation is simple -- just send a series of pulses.

## Re:Practical Applications/Uses? (Score:5, Funny)

If anything, anyone receiving the signal will wonder how you managed to build such a powerful transmitter when you haven't discovered binary numbers yet and are apparently using some sort of unary mathematics that really shouldn't work. They're bound to be disappointed when they find out you actually know about "0", but just weren't using it.

## Re:Practical Applications/Uses? (Score:2)

And just because aliens receive a signal with a bunch of strong, equally spaced pulses doesn't mean they'll automatically assume it's intelligent. There are plenty of natural cosmic phenomena which produce equally spaced pul

## Couldn't one just transmit the number of digits? (Score:2)

## A Mersenne Prime is... (Score:5, Informative)

Mn = 2^n - 1.

Mersenne primes have a connection with Perfect Numbers (numbers that are equal to the sum of their proper divisors) where by if M is a Mersenne prime, then M(M+1)/2 is a perfect number.

## Re:A Mersenne Prime is... (Score:2)

## Re:A Mersenne Prime is... (Score:5, Interesting)

You can say even more. If

... + 2^(a))

Mcan be written as 2^n- 1, thenMis said to be aMersenne number. IfMis also prime, then it is aMersenne prime. For 2^n- 1 to be a Mersenne prime,nmust be a prime number, since we have2^(ab) - 1 = (2^a-1)(2^(a(b-1)) + 2^(a(b-2)) +

For instance, 2^6-1 is (in binary) 111111 = 1001 * 111, as predicted by the above factorisation.

If

pis a prime number and if 2^p-1 is a Mersenn prime, then, as was pointed out above, 2^(p-1)(2^p-1), is a perfect number. Moreover, ifNis anevenperfect number, thenNcan be written (uniquely) as 2^(p-1)(2^p-1) wherepis a prime number and 2^p-1 is a Mersenne prime.Wikipedia [wikipedia.org] has a reasonably intelligible introduction to perfect numbers, and MathWorld [wolfram.com] contains a proof of why

everyeven perfect number must have the form claimed above.To see why

M= 2^(p-1)(2^p-1) is a perfect number whenp, 2^p-1 are primes, it suffices to note thats(n), the function that maps an integer to the sum of its divisors (e.g.s(6) = 1 + 2 + 3+6,s(8) = 1 + 2 + 4+8) ismultiplicativein the number-theoretic sense, that is to says(ab) =s(a)s(b) whenevera, bhave no prime factors in common. Then evaluatings(M) is simply a case of evaluating it on the factors, which are relatively prime since one is a power of 2, 2^(p-1), and the other is an odd prime, 2^p-1.s(2^p-1) = 2^p-1 + 1 = 2^p(since we have a prime number), and 2^(p-1) = 2^p-1 is an easy formula that is true of all powers of 2. Hences(M) = 2^p(2^p-1) = 2 ( 2^(p-1) (2^p-1) = 2s(M). That is to say, the sum of all the divisors ofMadd up to twiceM, and if we leave the divisorMitself out of the sum, we see thatMis a perfect number.## Re:A Mersenne Prime is... (Score:2, Funny)

Here.

2^64-1 for example.

111111111111111111111111111111111111111

Oh.

You want it represented in base 10?

## Re:A Mersenne Prime is... (Score:2)

## Mersenne Primes? Bah! (Score:5, Funny)

## Mersenne Primes - Definition (Score:2, Informative)

## Re:Mersenne Primes - Definition (Score:5, Insightful)

## Re:Mersenne Primes - Definition (Score:2)

A MP in binary would look like 10000000001, where the total number of binary digits is equal to the power of two.

## 3 = 11, 7 = 111 (Score:2)

## Re:3 = 11, 7 = 111 (Score:3, Funny)

## Re:Mersenne Primes - Definition (Score:2)

Pratically, they're mostly used in military-grade real-time encryption in the hash keys of secured phones.This sounds like some gobbledegook. Most Mersenne primes are too large and too rare to have any real cryptographic significance today. Can you back up this claim at all?

## Re:Mersenne Primes - Definition (Score:5, Informative)

2^2 = 4

4 - 1 = 3

2^3 = 8

8 - 1 = 7

2^4 = 16

16-1 = 15

## Probably silly reference (Score:5, Funny)

Lord Percy: "The King is dead! L-"

Prince Harry [interrupting]: "

Probablydead."Lord Percy: "The King is probably dead!"

## Spoiler alert about the number (Score:4, Funny)

Seriously, don't reead any farther....

It only has

twofactors.## MOD PARENT UP (Score:2)

## Woohoo! The world is saved! (Score:2, Funny)

Thank you Great Internet Mersenne Prime Search!

## Can't see the pattern? (Score:2, Funny)

42nd Mersenne Prime...## One practical use of Mersenne Primes... (Score:5, Interesting)

Prime95 (which searches for these primes) really puts a load on the CPU and raises the temperature in a hurry. It's commonly used to test the stability of overclocking configurations since it stresses the chip and is able to detect if there is an error in the computation.

Generally, if you can run Prime95 for 24 hours straight, most people will consider the overclocked PC a stable configuration.

## Re:One practical use of Mersenne Primes... (Score:3, Interesting)

Distributed.net has this to say on overclocking [distributed.net].

## Yes! (Score:5, Funny)

If this pans out, GIMPS will have been responsible for the eight current largest Mersenne Primes ever discovered.In your face, Photoshop!

## Two unknowns (Score:5, Informative)

This has not yet been confirmed, therefore there could be less than 42 known Mersenne primes.

Hovewer, according to MathWorld, there is a chance that it is not the 42nd Mersenne prime at all for another reason

"However, note that the region between the 39th and 40th known Mersenne primes has not been completely searched, so it is not known if M20,996,011 is actually the 40th Mersenne prime.."Looks like the big math guys don't exactly know how to count at all

## That brings back some memories... (Score:5, Interesting)

As part of the course, we studied Mersenne primes. At the time, I was dabbling in x86 assembler, and I decided to write a program to calculate the then largest known Mersenne prime number: 2^31 - 1, which worked out to 65,050 digits.

The size worked out perfectly, as in 1989 that meant it could fit into one 65KB segment on my blazing-fast 8Mhz 8088. As I recall, the runtime was about two days. The program still works--I can't remember how long it took to run on a 3Ghz P4, but I think it was just a few minutes.

I'm sure any competent programmer (read--not me) could calculate the result much faster, but at the time I was very proud of my little creation.

## Re:That brings back some memories... (Score:5, Informative)

As part of the course, we studied Mersenne primes. At the time, I was dabbling in x86 assembler, and I decided to write a program to calculate the then largest known Mersenne prime number: 2^31 - 1, which worked out to 65,050 digits.I don't think it actually did bring back those memories. 2^31-1 is 2147483647. You're thinking of Mersenne prime 31, which is 2^216091 - 1.

## Re:That brings back some memories... (Score:2)

## Re:That brings back some memories... (Score:4, Funny)

## ok now , back to protien folding! (Score:2)

im a geek...but damn...thats uber-geekish

## the trouble is (Score:3, Funny)

The number in question is currently being double-checked by George WoltmanOk...lets see here...

5465875133124687545551258898456556......9803480

2BUMMER!

## What an incredibly awesome... (Score:2, Insightful)

## Re:What an incredibly awesome... (Score:2)

## OMG! Do you know what this means!?!?! (Score:2, Funny)

.

.

No really, please tell me. I haven't a clue...

## Here's one good reason... (Score:3, Interesting)

Thought it takes my 1.7Ghz 3 months to test a 10mil digit prime.

## GIMPS vs The GIMP (Score:2, Funny)

These guys should sue each other for trademark infringement.

With any luck they'd both be forced to change their name to something sensible.

## Prime number bear (Score:2)

## Mixed results (Score:2)

Damn it! I have to change my luggage combination again. Darn you, George Woltman!

## This is news? (Score:2)

## Re:This is news? (Score:2)

And I assume you included the trick, but slashcode stripped it out before posting.Nope, federal gag order.

## Re:This is news? (Score:3, Funny)

## On a related note (Score:4, Informative)

## Organizer of Gimps? (Score:2)

The number in question is currently being double-checked by George Woltman, organizer of GIMPSSomehow, I don't think that the world will be threatened by George Woltman and his organized gimps.

## Full text of article (Score:4, Funny)

Read the rest of this comment...## Small steps (Score:4, Informative)

Please come join Folding@home [stanford.edu], we're actually doing something worth all that waste heat.

## meaning of life, bah (Score:4, Funny)

## so very interesting (Score:3, Funny)

The study of such numbers has a long and interesting historyReminds me of when Bart Simpson's 4th-grade class was forced by Principal Skinner to have their annual field trip take place at a box company (instead of the hoped for chocolate factory / fireworks outlet / circus):

## Re:Would a math geek... (Score:4, Informative)

A Mersenne prime is a Mersenne number, i.e., a number of the form

2^n - 1

that is prime. In order for it to be prime, n must itself be prime.

## Re:Would a math geek... (Score:5, Informative)

## Re:Would a math geek... (Score:2)

## Re:Would a math geek... (Score:5, Informative)

The reason that mersenne primes are usually the biggest is because for primes of this form, there is a primality test (Lucas-Lehmer) that is exceedingly efficient.

## Re:Great. Now what is it??????? (Score:3, Funny)

## Re:Great. Now what is it??????? (Score:2)

## Re:Great. Now what is it??????? (Score:2)

## Re:Great. Now what is it??????? (Score:3, Funny)

11111...1111

where "..." means some number of 1s.

## Re:Immoral use of computing power (Score:5, Funny)

Because of course aliens will feed us...

They even will bring a cookbook with them, "To Serve Mankind."

## Re:Immoral use of computing power (Score:2)

## Re:Immoral use of computing power (Score:2)

## Re:Immoral use of computing power (Score:2, Funny)

## Screw you AC (Score:2)

amgoing to eat them.## Re:If I do say so myself. (Score:2, Funny)