Author: Vincent Lejeune
Date: 14:23:07 05/26/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
>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,
>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.
Here's a really cool applet "Factorization using the Elliptic Curve Method"
http://www.alpertron.com.ar/ECM.HTM
>
>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.
>
>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 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.