On Thursday 11 December 2003 15:39, [EMAIL PROTECTED] wrote: > Let p > 2 be prime and Mp = 2^p - 1. > The familiar Lucas-Lehmer test sets a[0] = 4 > and a[j+1] = a[j]^2 - 2 for j >= 0. > Mp is prime if and only if a[p-1] == 0 mod Mp. > > When Mp is prime, then > > a[p-2]^2 == 2 == 2*Mp + 2 = 2^(p+1) (mod Mp). > > Taking square roots, either > > a[p-2] == 2^((p+1)/2) mod Mp > or > a[p-2] == -2^((p+1)/2) mod Mp. > > > Around 20 years ago I heard that nobody could predict > which of these would occur. For example, > > p = 3 a[1] = 4 == 2^2 (mod 7) > p = 5 a[3] = 194 == 2^3 (mod 31) > p = 7 a[5] = 1416317954 == -2^4 (mod 127). > > Now that 40 Mersenne primes are known, can anyone > extend this table further? That will let us test > heuristics, such as whether both +- 2^((p+1)/2) > seem to occur 50% of the time, and > provide data to support or disprove conjectures. > This is dependent on using the Lucas sequence starting at 4. In practice there are a large number of other starting values which could be used - in fact, 2^(p-2) of them. AFAIK we happen to use 4 because it is a "nice small number" which works for all values of p > 2 - whereas most of the other values which work for p don't neccessarily work for q != p.
For instance, with p=3 we could use starting value 3 instead of 4 3^2 - 2 = 7 is congruent to 0 modulo 2^3-1 4^2 - 2 = 14 is congruent to 0 modulo 2^3-1 But other values don't work: 0^2 - 2 = -2 is congruent to 5 modulo 2^3-1 1^2 - 2 = -1 is congruent to 6 modulo 2^3-1 2^2 - 2 = 2 is congruent to 2 modulo 2^3-1 5^2 - 2 = 23 is congruent to 2 modulo 2^3-1 6^2 - 2 = 34 is congruent to 6 modulo 2^3-1 Obviously enough, if k is a quadratic residue modulo n. then so is n-k (n-k)^2 mod n = n^2 -2kn +k^2 mod n = k^2 mod n So, in the penultimate step, it _doesn't matter_ whether the actual residue is 2^((p+1)/2) or -2^((p+1)/2) - if running one iteration from 2^((p+1)/2) doesn't give residue 0, then neither can running one interation from -2((p+1)/2), and vice versa. So simply testing whether 2^((p+1)/2)+2 is a quadratic residue modulo 2^p-1 _might_ (in principle) be helpful. Look in particular at p=11. 2^6+2 = 66 (not 68 as misprinted in my previous message) appears not to be a quadratic residue modulo 2^11-1 = 2047 and sure enough 2^11-1 is composite. Interestingly there are _two_ distinct solutions to x^2 mod 2^23-1 = 2^12+2: x=+/-2339992 & x=+/-3053916. This suggests that the number of starting values for a "successful" L-L test might _exceed_ 2^(p-2) by a factor of _at least_ 2 i.e. every possible starting value would have to reach 0 after p-2 iterations - which is clearly absurd. So perhaps the criterion should be that there is only one _distinct_ solution to sqrt (2^(p+1)/2)+2) modulo 2^p-1. Anyhow if we "play safe" we simply find that, in the case p=23, 4098 is a quadratic residue mod 8388607, so we have to run a LL test. Unless we happen to notice that 23 is a 3 mod 4 Sophie-Germain prime so 8388607 is divisible by 47.... Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
