45th Known Mersenne Prime Found? 396
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!"
GPU's? (Score:5, Interesting)
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:Forgive my ignorance (Score:3, Interesting)
I guess there's some room to ask... (Score:2, Interesting)
... why the EFF considers it worth $100,000 of donated funds to pay someone for finding a 10,000,000-digit prime number. That is not what my donations were intended to do.
Go fix warrantless wiretapping, then go looking for prime numbers, kthxbye.
Re:GPU's? (Score:5, Interesting)
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 (Score:5, Interesting)
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.
Moore-Otsuka-Helkenberg prime number sieve (Score:2, Interesting)
My friends and I wrote a unique prime number sieve, using previously unknown numerological techniques (exploiting digital roots).
You can find our sieve here:
http://jessicalogsdon.com/page5/page5.html [jessicalogsdon.com]
We are currently turning our sieve in a method for rapidly factoring semi-prime numbers. Digital root mechanics have certain properties that make it easy to identify semi-prime candidacy positions in a by-9 table of the natural numbers.
A PDF at the bottom of the above-linked site explains our latest investigation of solving for [p, q] where n = p*q. The source code on the page is our prime sieve implemented in Perl.
Big Money! No Whammy! You, too, could become a hundred-millionaire M.O.H.'ing RSA to the ground!!
Re:What would really be neat... (Score:3, Interesting)
The number of digits in a Mersenne prime is always a prime number, if it's written in base 2 ;)
Re:Forgive my ignorance (Score:2, Interesting)
If you were to find a 10,000,000 digit prime today the above rules imply that $3,333 would go to Michael Cameron, discoverer of the 39th known Mersenne prime, $3,333 would go to Michael Shafer, discoverer of the 40th known Mersenne prime, $3,333 would go to Josh Findley, discoverer of the 41st known Mersenne prime, $3,333 would go to Dr. Martin Nowak, discoverer of the 42nd known Mersenne prime, $6,667 would go to Curtis Cooper and Steven Boone the discoverers of the 43rd and 44th known Mersenne prime, $5,000 would go to GIMPS, $25,000 would go to charity, and $50,000 would go to you.
This is great news, I've been crunching Mersenne numbers myself and it's nice to finally see a potential >10M digit one.
Re:Moore-Otsuka-Helkenberg prime number sieve (Score:2, Interesting)
It is actually more efficient than the classical Sieve of Eratosthenes. Our geometric candidacy pattern eliminates all numbers divisible by 2, 3, and 5 much faster than does the Sieve of Eratosthenes (the Sieve of Atkin, I think, does something similar algebraically).
I didn't say we have the fastest sieve in the world, just that we have a new sieve.
The operation of the sieve is actually very accommodating to parallelization, so maybe this sieve provides benefits in that area.
By "numerology" I meant "repeated digit sum", because that's what stupid people understand it as: adding everything up in a word to a single number (in our case, words with letters are instead numbers with digits). The process of addition (or in our case, remainder mod 10) requires no spiritualism.
There is no such thing as digital roots [wikipedia.org]?
Certainly there's nothing new here... I don't doubt that the Mayans knew this stuff -- but they didn't have RSA-2048!
Re:Forgive my ignorance (Score:2, Interesting)
Re:What would really be neat... (Score:4, Interesting)
You mean this?
2^2-1=3 (prime)
2^3-1=7 (prime)
2^7-1=127 (prime)
2^127-1=170141183460469231731687303715884105727 (prime)
2^170141183460469231731687303715884105727-1="universe overflow" (is it prime? doubtful!)
Perfect numbers and Mersenne Primes (Score:5, Interesting)
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 (Score:5, Interesting)
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
Re:What would really be neat... (Score:2, Interesting)
1^2-1 = 1 (prime)
1^2-1 = 1 (prime)
1^2-1 = 1 (prime)
1^2-1 = 1 (prime)
1^2-1 = 1 (prime)
Re:What would really be neat... (Score:3, Interesting)
But what if the base was also prime?
Ooh, ooh, what if the number of all the possible bases (less than the number itself) such that the number of digits of the representation of the prime number was also a prime number? How about all the number of prime bases?
Maths is fun, even if not always useful.