Author: Tord Romstad
Date: 03:10:05 05/28/05
Go up one level in this thread
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. :-)
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.