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?
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.
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: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 the students should release the problems over a network, and have home users calculate the answer for them. It'd save the Universities a lot of money.
I don't think it would work for code cracking, or government projects, as these contain sensitive information.
Here's one good reason... (Score:3, Interesting)
Thought it takes my 1.7Ghz 3 months to test a 10mil digit prime.
Re:A Mersenne Prime is... (Score:5, Interesting)
You can say even more. If M can be written as 2^n - 1, then M is said to be a Mersenne number. If M is also prime, then it is a Mersenne prime. For 2^n - 1 to be a Mersenne prime, n must be a prime number, since we have
... + 2^(a))
2^(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 p is 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, if N is an even perfect number, then N can be written (uniquely) as 2^(p-1)(2^p-1) where p is 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 every even perfect number must have the form claimed above.
To see why M = 2^(p-1)(2^p-1) is a perfect number when p, 2^p-1 are primes, it suffices to note that s(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) is multiplicative in the number-theoretic sense, that is to say s(ab) = s(a)s(b) whenever a, b have no prime factors in common. Then evaluating s(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. Hence s(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 of M add up to twice M, and if we leave the divisor M itself out of the sum, we see that M is a perfect number.
Re:One practical use of Mersenne Primes... (Score:3, Interesting)
Distributed.net has this to say on overclocking [distributed.net].