45th Known Mersenne Prime Found?

An anonymous reader writes "The Great Internet Mersenne Prime Search (GIMPS) has apparently discovered a new world-record prime number. A GIMPS client computer reported the number on August 23rd, and verification is currently under way. The verification could take up to two weeks to complete. The last Mersenne prime discovered was over 9.8 million digits long, strongly suggesting that the new value may break the 10 million digit barrier — qualifying for the EFF's $100,000 prize!"

Comments

GPU's?

[EdIII]

Testing a single 10,000,000 digit number takes two months on a 2 GHz Pentium 4 computer

According to their own benchmark pages a newer Core 2 Duo E8500 process in less than 21 days. Just recently I know that password cracking programs were written to use GPU's which dramatically increased the performance. Wouldn't writing code to run this on the GPU's result in even faster processing times?

Re:GPU's?

[fredrikj]

The Lucas-Lehmer test for Mersenne primes consists of repeated multiplication (modulo a fixed large number). Large-integer multiplication is done via floating-point FFT, which is nothing but massive amounts of operations on small numbers. I don't know how FFT implementations for GPUs compare, but intuitively I think they ought to be at least as fast as for CPUs. The primes tested by GIMPS are small enough to fit entirely in GPU memory, so latency doesn't seem like a problem.

(I don't really know much about any of this, so feel free to correct/enlighten me.)

Re:Forgive my ignorance

[mochan_s]

It goes towards the enormous knowledge on prime number theory.

The problem of if there is a pattern to the sequence of prime numbers is unknown. That is, if I ask you what is the 69th prime number, the only known general algorithm is to computer the 1st prime, 2nd prime and so on until the 69th prime. And, also there are unsolved problems with Mersenne primes as well.

So, if someone comes up with a good theory, then it's good to have some big examples.

And, in case you didn't know, prime number theory is used in cryptography.

Perfect numbers and Mersenne Primes

[spaceyhackerlady]

Another fun relationship is between Mersenne Primes and Perfect Numbers, numbers whose factors add up to themselves.

If 2^n-1 is prime, (2^n-1)(2^(n-1)) is perfect (and has a distinctive pattern of digits in binary, to boot...). The proof in this direction is easy. Proving that all even perfect numbers are of this form is a little harder, but doable.

The hard one is proving whether or not there are any odd perfect numbers, and, if so, what form they might take. Nobody has done this yet.

...laura

Re:Forgive my ignorance

[David Gould]

My favorite incarnation of that joke has the mathematician saying "THERE IS A SOLUTION!"

Try: "A solution exists." For the punchline to work best, use the math lingo as it would be used in a real proof. Also, since he was a theoretical mathematician, he didn't do "a lot of complicated math", he "looked at the fire, looked at the bucket of water [*1], concluded that 'a solution exists', and went back to sleep".

It's amazing to me that it's possible to know that there is a solution, but not know what it is. Kudos, math people :)

Heh -- when you put it that way, it does seem kinda weird, but it's really not that hard to explain how it works: the key is that the task of figuring out whether or not a solution exists for one problem can itself be taken as an entirely different problem, so if you just solve that one instead of the original one, there you are. And those "meta-problems" tend to be both much easier in terms of actual computation required and much more "interesting" [*2] in terms of conceptual effort required, which is why mathematicians prefer to focus on them. And yes, it works recursively (figuring out whether or not it's possible to determine whether or not a solution exists for a particular problem, and so on...)

[1] one of which, the GP forgot to mention, was conveniently in each room

[2] in math lingo, i.e., "harder" in normal terms