Author: Vincent Diepeveen
Date: 05:53:53 05/27/05
Go up one level in this thread
On May 27, 2005 at 08:28:12, Vincent Diepeveen wrote:
>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.
^^^^
Multiplications rather for fermat2 is the extra cost. For mersenne numbers there
are P multiplications involved. For random prime p/2.
>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 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.