Author: Tord Romstad
Date: 13:37:48 05/26/05
Go up one level in this thread
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. 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.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.