Hi, I was thinking about the possible reversibility of the Lucas Lehmer algorithm. In particular, for any odd number n > 1,
(2^((n+1)/2))^2 is congruent to 2 modulo 2^n-1 i.e. 2 is a quadratic residue modulo 2^n-1. This is not helpful in itself as (a) there are other integer solutions to sqrt(x + k.2^n-1) = 2, (b) it does not distinguish in any way between prime and composite Mersenne numbers. However, considering the next-to-the-last iteration appears to be interesting. If x is a solution to (x^2 - 2) mod (2^n-1) = 2^((n+1)/2) then starting from residue x and performing 2 iterations will result in residue 0. For small n>3 (n=3 does not work because there is only one iteration to do in the L-L test!) we have: n = 5: x^2-2 mod 31 = 8; x^2 mod 31 = 10; x = 14, x = 17 n = 7: x^2-2 mod 127 = 16; x^2 mod 127 = 18; x = 48, x = 79 n = 9: x^2-2 mod 511 = 32; x^2 mod 511 = 34; no solutions n = 11: x^2 - 2 mod 2047 = 64; x^2 mod 2047 = 68; no solutions n = 13; x^2 - 2 mod 8191 = 128; x^2 mod 8191 = 130; x = 3470, x = 4721 n = 15; x^2 - 2 mod 32767 = 256; x^2 mod 32767 = 258; no solutions n = 17; x^2 - 2 mod 131071 = 512; x^2 mod 131071 = 514; x = 19647, x = 111424 n = 19; x^2 mod 524287 = 1026; x = 199279, x = 325008 n = 21; x^2 mod 2^21-1 = 2050; no solutions n = 23; x^2 mod 2^23-1 = 4098; x = 2339992, x = 3053916, x = 5334691, x = 6048615 In other words, it looks as if when there are no solutions to x^2 mod 2^n-1 = 2^((n+1)/2) + 2, then 2^n-1 is not prime, although the converse is not neccessarily true. (1) Could someone with the required background please tidy up my logic and prove that the assertion above is true i.e. there is no prime 2^p-1 with p > 3 such that there are solutions to x^2 mod 2^p-1 = 2^((p+1)/2) + 2 If so, then we have a "one-step" test which would allow us to eliminate some - possibly many - Mersenne prime candidates without even bothering to look for small factors. (2) Can it be demonstrated that the search for solutions of x^2 mod 2^p-1 = 2^((p+1)/2) + 2 - or at least the search for _existence_ of solutions (we wouldn't need the actual numerical values) - might be faster than executing the LL test? The method I used for small n above was just to step through values of k calculating k^2 mod 2^n-1, which is clearly exceedingly _in_efficient for large n! Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
