Author: Tord Romstad
Date: 07:37:50 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:
>
>>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?
What indoctrination attempt are you talking about? I provided a link to
the GIMPS site in order to inform about the hardware and software used to
find the currently biggest known prime number, and also because it contains
a number of useful links for those who are interested in learning more
about Mersenne primes and prime numbers in general.
>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.
I couldn't care less who or what finds the first 10 or 100 million digit
prime number. World record prime numbers in themselves hold absolutely
zero interest for me.
However, I do have a strong interest in algebraic number theory (although
it is not my field of research), and therefore know a fair bit about the
mathematics behind the various techniques for factorization and primality
testing (I am not an expert, though). That the theory can be used to
create computer programs which can factor really big numbers and find
enormous prime numbers is just a curiosity, nothing more. Actually spending
thousands of CPU hours hunting for new world record prime numbers seems like
a tremendous waste of time to me.
I don't care who finds the next big prime number, how much time the
computation is likely to take, or even if a new world record prime is
ever found. On the other hand, I *do* care if somebody is able to prove
that there are infinitely many Mersenne primes, that no Mersenne number
is divisible by a square, or that there are no odd perfect numbers. This
is the kind of questions I am interested in.
>Factorization goes faster than proving,
I am sure you meant to say the opposite, as is evident from the rest of
your post. Testing whether a big number is prime is much less work than
actually factoring the number (which is also intuitively obvious).
>>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.
That's exactly what I said in the paragraph you quote.
>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");
You must have a bug or a typo somewhere, I think. The code above will
definitely not work. It fails even for p=5, as you can verify just by
calculating in your head.
>The fastest probabilistic test possible for a special prime will most likely be
>not faster than Lucas-Lehmer.
This is probably correct, but of course the probabilistic tests have
the obvious advantage that they work for all numbers, not just Mersenne
numbers.
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.