Author: Vincent Diepeveen
Date: 08:06:32 05/27/05
Go up one level in this thread
On May 27, 2005 at 11:04:02, Vincent Diepeveen wrote:
>On May 27, 2005 at 10:37:50, Tord Romstad wrote:
>
>>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.
>
>"world record primes are always Mersenne primes"
>
>that's a very rude statement and just wasn't true in the past and most likely
>won't be true in the future either. the GIMPS project has what is it, a record
>of 5 or 6 primes now at their conto?
>
>This because they hardly have any competition.
>
>>>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.
>
>I am not careless about such huge achievements.
>
>>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.
>
>Please tell me, what do you consider useful ways to spend system time?
>
>Note that research after new medicines and other bio-medical researches eats
>less than 0.5% system time.
>
>I remember a research, trying to predict the future height of the ocean, running
>on a big 1024 processor supercomputer here in Netherlands. After putting in half
>a million hours of cpu time (yes that was many months of non stop computing at
>hundreds of processors), they concluded that the sea would rise 1 meter.
>
>1 month later i found in a logfile of them: "small initialisation bug, we
>initialised the ocean water height 1 meter too high".
>
>But was it wasted system time?
>
>The researchers got their publicity world wide and their own discovery show that
>the ocean floor 'soon' will rise 1 meter.
>
>>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).
>
>Please reread what i wrote. It's far easier to get rid of a big % of composites
>by first factorising. To prove 1 number you'll have to do a million or 33+
>million FFT calculations.
>
>To factorize, he perhaps you're already done quickly, perhaps it's dividable by
>23 who knows?
>
>Hmm let's see 2^11 = 2047 ==> dividable by 23 :)
>
>That's a far faster way to see whether something is a composite than doing the
>lucas-lehmer test.
>
>>>>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)
(mod m)
>>> 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.
>
>Bugfix your head :)
>3
>9
>19
>20
>28 <==> p-3 = 31 - 3 = 28
>
>>>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 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.