Re: Mersenne: M(2) - composite?!
> 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
Re: Mersenne: M(2) - composite?!
-Original Message- From: Nathan Russell <[EMAIL PROTECTED]> To: [EMAIL PROTECTED] <[EMAIL PROTECTED]> Date: 31 July 2001 19:51 Subject: Mersenne: M(2) - composite?! >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. >From <http://mersenne.org/math.htm> (brackets and exponentiation added for the sake of clarity) The Lucas-Lehmer primality test is remarkably simple. It states that 2**P-1 is prime if and only if S(p-2) is zero in this sequence: S(0) = 4, S(N) = S(N-1)**2 - 2 mod 2**P-1. If P=2 then S(P-2) is S(0) is 4 which is clearly not 0. It's not even 0 mod 3 However <http://www.utm.edu/research/primes/mersenne.shtml#test> does state the P must be odd. So I guess the mersenne.org page is wrong. >Nathan Daran _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: M(2) - composite?!
How did you get -1? Lucas-Lehmer Test: For p odd, the Mersenne number 2p-1 is prime if and only if 2p-1 divides S(p-1) where S(n+1) = S(n)2-2, and S(1) = 4. You missed the premise "for p odd". And even so, S(p-1)/(2p-1) with p = 2; S(1)/3 = 4/3. Carleton - Original Message - From: "Nathan Russell" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Tuesday, July 31, 2001 2:19 PM Subject: Mersenne: M(2) - composite?! > 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. > > Nathan > _ > Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm > Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers > _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: M(2) - composite?!
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. Nathan _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
