Author: Vincent Diepeveen
Date: 08:22:46 05/27/05
Go up one level in this thread
On May 27, 2005 at 11:15:39, Uri Blass wrote:
>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)
>>>> 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
>
>I guess you meant t=t*t(mod m) and not t=(t*t)mod p
correct. in my writings i usually assume p is the prime, that's why the
confusion took place. my fault.
And because Tord is interesting in proving things, he'll have to prove
that for a composite p there doesn't exist a number s wherefore holds that:
s*s = p-3 (mod p)
and given p = 2^n - 1 AND n is prime
BTW i'm more interested in finding that big number and cashing in the honour :)
Vincent
>Uri
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.