Author: Vincent Diepeveen
Date: 08:50:54 05/29/05
Go up one level in this thread
On May 28, 2005 at 06:10:05, Tord Romstad wrote:
>On May 27, 2005 at 11:22:46, Vincent Diepeveen wrote:
>
>>On May 27, 2005 at 11:15:39, Uri Blass wrote:
>>
>>>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.
>
>Yes, easy mistake to make. With 'mod p' replaced by 'mod m', your
>code indeed looks correct. In fact it is just a slightly different
>forumlation of the classical Lucas-Lehmer test. Here is the
>corrected code you posted elsewhere in the thread:
>
>>// Diepeveen test to find mersenne primes
>>// test whether p is prime p = 2^n - 1
>>// when given n is prime
>>
>>t = 3;
>>for( j = 1 ; j < n ; j++ )
>> t = t*t; // mod p
>> if( t == p-3 ) printf("prime\n"); else printf("composite\n");
>
>And here is how the classical Lucas-Lehmer test would look in the
>same type of pseudo-C (I may have made a small mistake or two,
>too many drinks and not enough sleep last night):
>
>// Lucas-Lehmer test to find mersenne primes
>// test whether p is prime p = 2^n - 1
>// when given n is prime
>t = 4;
>for(j = 1; j < n; j++)
> t = t*t - 2; // mod p
>if(!t) printf("prime\n"); else printf("composite\n");
>
>The differences are very small, as you can see, but arguably your
>method is a tiny bit more elegant. :-) The correctness of both
>variants can be proved in exactly the same way.
>
>>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
>
>I am about to leave town for a couple of days and have no time to write
>out a detailed proof in ASCII, but this can be proved in a relatively
>straightforward way by the same techniques used to prove the
>correctness of the Lucas-Lehmer test. A sketch of the proof:
>
>First, assume that p is composite and that a number s with the required
>properties exists. Using your number s, you can construct a primitive
>nth root of 1 in the ring Z/(p) (this is probably the most tricky part of
>the proof). Because p is composite, it must have a prime factor q
>less than or equal to the square root of p. Let G be the group of units
>in k[sqrt(-3)], where k is the field with q elements. It is clear that G
>has at most q^2 - 1 < p elements. Replacing s with s mod q and
>considering s as an element of G, we get an element of G with
>order p. Because the order of G is less than p, this is not possible.
>
>>BTW i'm more interested in finding that big number and cashing in
>>the honour :)
>
>Feel free to do that, I won't try to stop you. If you promise that
>you will not beat me at proving that there are infinitely many
>Mersenne primes, I will promise that I won't try to beat you
>at finding the next world record prime. :-)
Please note it has been proven already quite a while ago there is infinitely
many Mersenne primes.
The insight there are infinitely many is trivial anyway.
>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.