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.
Peter Montgomery
_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
