> From: Nathan Russell <[EMAIL PROTECTED]>
> Hi all,
>
> I'm a bit puzzled. The other day, I donated blood and kept my mind
> busy by doing LL tests on a few exponents mentally. I kept getting
> the result that the LL test for M(2) ends up resulting in a repeating
> value of -1, and certainly cannot ever become zero. Am I missing
> something really obvious? I confirmed it on paper later to make sure
> I didn't make a mistake in the mental math.
One proof of the LL test notes that if we define
a[0] = 4
a[j+1] = a[j]^2 - 2 (j >= 0)
then
a[j] = (2 + sqrt(3))^(2^j) + (2 - sqrt(3))^(2^j) (j >= 0)
This is a simple induction argument. Next, if
alpha = (1 + sqrt(3))/sqrt(2)
beta = (1 - sqrt(3))/sqrt(2)
then
alpha^2 = 2 + sqrt(3)
beta^2 = 2 - sqrt(3)
alpha*beta = -1
so
a[j-1] = alpha^(2^j) + beta^(2^j) (j >= 1)
If N = 2^p - 1 is prime, and p >= 3 is odd, then N == 7 (mod 24).
Therefore 2 is a quadratic residue (indeed, 2^((p+1)/2) is a square
root of 2 modulo N) but 3 is a quadratic nonresidue.
alpha and beta are algebraic conjugates in GF(N^2).
So alpha^N = beta and beta^N = alpha (mod N).
Since alpha*beta = -1, this implies
alpha^(N+1) == beta^(N+1) == -1 (mod N)
and a[p-1] == alpha^(N+1) + beta^(N+1) == -2 (mod N) .
Therefore a[p-2] == 0 (mod N).
When p = 2 and N = 3, we can neither claim that 2 is a
quadratic residue nor that 3 is a non-residue.
Both alpha and beta reduce to 1/sqrt(2) mod 3.
As in the case where p is odd, alpha and beta
are in the extension field GF(N^2) and not the base field GF(N).
Unlike that case, alpha = beta rather than alpha = beta^N and beta = alpha^N.
The proof falls apart.
Peter Montgomery
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
