42nd Mersenne Prime Probably Discovered

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

Re:Would a math geek...

[haluness]

From mathworld (whose link is in the summary)

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

[Smallpond]

A Mersenne number is all ones when written in binary. If its prime, it is a Mersenne prime.

Re:Would a math geek...

[IvyMike]

A prime of the form (2^n)-1. This means that in binary, it's a big string of "1"s.

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.

A Mersenne Prime is...

[vivin]

A mersenne Prime is a prime number that is one less than the power of two. Hence:

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.

Mersenne Primes - Definition

[Un-Thesis]

A Mersenne Prime is where the prime number also fulfills the equation 2^P - 1 2^2 - 1 = 3 ... 3 is a mersenne prime. 2^3 - 1 = 5 ... 5 is a mersenne prime. 2^4 - 1 = 7 ... 7 is a mersenne prime. The next one is 31 and after that 127. From there they get quite rare (only 42 known). They are VERY useful in cryptography and quantum physics...both deal with huge numbers. They are also used in some SETI applications because if you wanted to send primes, you'd probably send mersennes as these would be *very* non-random. Pratically, they're mostly used in military-grade real-time encryption in the hash keys of secured phones.

Re:Uses?

[Jeremy Erwin]

Testing distributed primality algorithms. I should have thought this was obvious.

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.

Two unknowns

[MaGogue]

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 ;)

Re:Practical Applications/Uses?

[mctk]

Large primes, of around 75-100 digits, are useful in encryption. Huge primes (i.e. over 7 million digits) are not currently useful in themselves, although we certainly learn more about mathemathics and computers as we try to find them.

Re:Practical Applications/Uses?

[robbyjo]

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?

[vivin]

It's a mathematical curiosity in some cases - just to find it for the sake of finding it, or for the glory of finding it. You know, like being the first to do something cool.

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:Mersenne Primes - Definition

[Anonymous Coward]

A Mersenne Prime is where the prime number also fulfills the equation 2^P - 1 2^2 - 1 = 3 ... 3 is a mersenne prime. 2^3 - 1 = 5 ... 5 is a mersenne prime. 2^4 - 1 = 7 ... 7 is a mersenne prime.

Were you up late last night or something? 2^3 - 1 is NOT 5. 5 is NOT a Mersenne prime. 2^4 - 1 is NOT 7. 7 is a Mersenne prime, though. You suck at math.

Re:That brings back some memories...

[djmurdoch]

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:Mersenne Primes - Definition

[SwansonMarpalum]

Might want to check your math:

2^2 = 4
4 - 1 = 3

2^3 = 8
8 - 1 = 7

2^4 = 16
16-1 = 15

On a related note

[OverlordQ]

Seventeen or Bust [seventeenorbust.com] (a distributed attack on the Sirpinski Problem), found the fourth largest (well fifth if this one pans out) prime at the beginning of this year, which contains 2,357,207 digits.

28433 * 2^7830457 + 1

List of all of the largest primes can be found here [utm.edu]

Re:GOOD QUESTION!

[Surt]

It's one step closer to proving there's an infinite sequence of these numbers. Just infinity - 42 more to go and the proof is complete!

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.

Small steps

[Duncan3]

One small step for mathematics, one giant leap for global warming :)

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

Re:binary

[mldl]

2 (as per usual) is a special case. 5 and 13 aren't mersenne numbers and therefore aren't in the list. Those numbers are the "exponent" as in 2 to the power of 5 minus 1 = 31 and 2 to the power of 13 minus 1 = 8191 are both mersenne primes and are both strings of 1 in binary.

Re:That brings back some memories...

[Anonymous Coward]

If you knew some math, you'd know that 2^n actually has 0.30103*n decimal digits.

Re:Uses?

[whizzard]

The theory is that there is an infinite number of these numbers

Actually, this theory has already been proven [mathforum.org].

Re:Uses?

[naff]

Wrong theory. That is for primes in general. "These numbers" refers to just the Mersenne primes [wolfram.com].

Re:Uses?

[Seculus]

That's not actually the argument for why the number of primes is infinite. Rather, assume there are only finitely many prime numbers. Multiply all of them together. Add one to this number. It is easy to show that this number is not divisible by any of the finitely many primes you started with. Hence it must be a prime number as well.

Re:correct me if i'm wrong

[Anonymous Coward]

The best general purpose primality tests are indeed probabilistic, but GIMPS uses a special purpose deterministic algorithm that checks if Mersenne numbers (those of the form 2^n-1) are prime. In fact, a general purpose algorithm would have trouble with numbers this big. I am sure this is explained in detail in their website.

Re:GOOD QUESTION!

[Artifakt]

What use are they?
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 starting from whatever patterns we might discover about Merseinnes.
We are spending a lot more on developing specific quantum computing applications that just may eventually lead to cracking that same problem. Given the relative budgets involved, if the Merseinne approach has even 1/1,000th of the chance of success it is still very cost effective (or we're spending way to much on quantum computing related crypto research).

Re:Uses?

[novakyu]

Actually, this theory has already been proven [mathforum.org].

IMNSHO, but that was the worst 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?

[rbrito]

One of the most obvious uses for having tasks like this is to understand better the problems and to develop better algorithms.

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 mind when they say "scalability) and if we have algorithms that help expose details of the problem being solved, it will only help us to design faster algorithms.

And these techniques may, with some adaptation, be used for solving other problems, not only the problem in question.

I hope that this helps you understand why some people are always concerned with developing good algorithms and also testing them in practice.

If you are interested in knowing more about the design of algorithms, please don't hesitate to ask.