Author: Vincent Diepeveen
Date: 05:28:12 05/27/05
Go up one level in this thread
On May 26, 2005 at 16:37:48, Tord Romstad wrote:
>On May 26, 2005 at 14:18:37, Sune Fischer wrote:
>
>>On May 26, 2005 at 13:15:04, Dann Corbit wrote:
>>
>>>On May 26, 2005 at 12:02:37, Vincent Diepeveen wrote:
>>>[snip]
>>>>Hello, i can calculate prime numbers up to 10 million digits at my pc nearly,
>>>>though not within 5 minutes.
>>>
>>>Less than a second, I imagine.
>
>Dann, I think you misunderstood. Calculating all prime numbers up to 10
>million DIGITS is a much more time-consuming task than calculating all
>prime numbers below 100 million (8 digits), as I am sure you agree. :-)
>>That's quite an imagination since there aren't any known primes that large :)
>
>You are right. The largest currently known prime number has 7,816,230 digits.
>There are now five known prime numbers with more than one million digits.
>
>>Last I checked only a handful or so had been found with more than a million
>>digits, and of course only through weeks of massively parallel super computer
>>power.
>
>It's not quite that bad. The current record prime was found on a single-CPU
>P4 2.4 GHz in 50 days. See the GIMPS ("Great Internet Mersenne Prime Search")
>page for details:
>
>http://www.mersenne.org/prime.htm
>
>Note that the world record primes are always Mersenne primes, i.e. prime
How much money are you willing to bet on this indoctrination attempt by the
GIMPS guys?
GIMPS is like Gnuchess, they won't be staying forever on top.
The advantage they had so far was that if you give all the 70000 computers or so
that are joining their prime search a job, that in a complete brute force
minimax way they can start proving the primes. Already in the 10 million digit
range they show how much of a problem they have with that.
It's likely that GIMPS will be the first to find a 10 million digit prime. I'm
not so sure whether it will be GIMPS finding a 100 million digit prime though.
Factorization goes faster than proving, and with Mersenne numbers it's nearly
impossible to factorize them all. At most 50% or so you can factorize, the other
50% of all prime exponents you'll have to prove in the dead slow way.
Additional there are real little mersenne prime numbers within a given range, so
the extra calculation work needed is overwhelming just to find 1 prime.
The major advantage GIMPS has is that in order to win the money, see
http://www.eff.org/awards/coop.html, you will need to prove the prime.
And the theory how to do that for mersenne numbers has been done already.
That's different to showing a likelyness of
99.99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999%
odds that it is a prime.
In fact with 1 simplistic tests (which indeed take a year on a single cpu) there
is about a million 9's or so in the chance it's a prime :)
It is pretty cruel from http://www.eff.org/awards/coop.html to demand a prove
for the prime instead of a likelyness in order to get the money.
If you have to show at least
99.99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999%
likelyness, then obviously 'industry grade primes' will win all those prizes and
not GIMPS.
>numbers of the form 2^p - 1, where p is a prime number. For numbers of
>this form, there exists an extremely fast and simple test for primality,
>known as the Lucas-Lehmer test.
>Here is a naive implementation of the Lucas-Lehmer test in Common Lisp:
>(defun mersenne-prime-p (p)
> "Tests whether 2^P - 1 is a prime, assuming that P is prime."
> (loop with n = (- (expt 2 p) 1)
> for i from 2 to p
> for s = 4 then (mod (- (* s s) 2) n)
> finally (return (= 0 s))))
>
>I compiled this without optimization in Macintosh Common Lisp, a Lisp
>implementation which is not known for being particularly fast with
>bignum calculations. Even so, proving that 2^11213 is a prime
>(3376 digits) took only 20 seconds on my iMac G5 1.8 GHz. By
>optimizing the code and choosing a compiler with faster bignum
>arithmetics it should be easy to push this below one second.
>For primes not of the form 2^p - 1, there is no test nearly as powerful
>as the Lucas-Lehmer test. As far as I know, the most efficient known
>algorithm is ECPP (elliptic curve primality proving). Using this test,
Let's not confuse a special type prime with general primes. Most 'tests' work
for all primes. Lucas-Lehmer works ONLY for mersenne.
With some highschool math i found another way to quickly determine Mersenne
numbers with a big exponent:
// test whether m = 2^p - 1 is prime, note p is also prime.
t = 3;
for( j = 1; j < p ; j++ )
t = t*t; (mod p)
if( t == p-3 ) printf("prime\n"); else printf("composite\n");
No need for Lucas-Lehmer when big exponents are involved :)
>proving that a 3000-digit number is a prime would probably take a
>few weeks on a modern desktop computer. Quite a long way from
>the 20 seconds used by my simple program above! By the way,
>ECCP and the theory of elliptic curves in general is a really cool
>subject, and well worth reading about.
For special case primes there are tests similar to Lucas-Lehmer, but nearly all
of those primes are in the form of p = x * y^a - i.
Where y is 2.
>I should also point out that there are probabilistic primality tests
>which are much faster. You can quickly determine that a really
>huge number is *almost* certainly a prime.
Probabilistic tests are slower than Lucas-Lehmer usually. For fermat2 you need 2
times more squares than Lucas-Lehmer eats. Squares are expensive.
The fastest probabilistic test possible for a special prime will most likely be
not faster than Lucas-Lehmer.
>Finding all primes with less than 10 million digits is of course not
>possible within 5 minutes, nor in 5 billion years. Just consider
>how many numbers you have to test, and multiply this number
>by the time you need for each primality test, and you will end up
>with a length of time which dwarfs the age of the universe. This
>remains true even if we are content to just search for probable
>primes.
>Tord
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.