mersenneforum.org > Math Can zero be an "intermediate step" value in Lucas-Lehmer?
 Register FAQ Search Today's Posts Mark Forums Read

 2012-02-03, 02:23 #1 That Don Guy   Feb 2012 28 Posts Can zero be an "intermediate step" value in Lucas-Lehmer? When going through the P-2 recursions to determine if 2^P-1 is prime using Lucas-Lehmer, is it possible that you can get zero as a value before the (P-2)th step? Are there any known examples of this? I already realize that if 0 is an intermediate step, then the number cannot be prime (since the next step is 0^2 - 2 = (N-2) mod N, then (N-2)^2 - 2 = 2 mod N, and 2^2 - 2 = 2 mod N, so there will never be a zero term).
2012-02-03, 07:41   #2
ckdo

Dec 2007
Cleves, Germany

232 Posts

Quote:
 Originally Posted by That Don Guy When going through the P-2 recursions to determine if 2^P-1 is prime using Lucas-Lehmer, is it possible that you can get zero as a value before the (P-2)th step? Are there any known examples of this? I already realize that if 0 is an intermediate step, then the number cannot be prime (since the next step is 0^2 - 2 = (N-2) mod N, then (N-2)^2 - 2 = 2 mod N, and 2^2 - 2 = 2 mod N, so there will never be a zero term).
An all time favourite.

Quote:
Originally Posted by Prime95
Quote:
 Originally Posted by asdf Is it possible for an LL test running accurately to go to 0, 1, or 2 before completion?
No. And a check every iteration would be real cheap.

2012-02-03, 09:18   #3
NBtarheel_33

"Nathan"
Jul 2008
Maryland, USA

5·223 Posts

Quote:
 Originally Posted by That Don Guy When going through the P-2 recursions to determine if 2^P-1 is prime using Lucas-Lehmer, is it possible that you can get zero as a value before the (P-2)th step? Are there any known examples of this? I already realize that if 0 is an intermediate step, then the number cannot be prime (since the next step is 0^2 - 2 = (N-2) mod N, then (N-2)^2 - 2 = 2 mod N, and 2^2 - 2 = 2 mod N, so there will never be a zero term).
I believe (and I might be wrong <preemptively ducks Bob>) that this is a consequence of the group theory underlying the LL test. Reaching 0 before the final step of an LL test would imply the existence of a nontrivial proper subgroup of a group of prime order, which would contradict Lagrange's Theorem.

2012-02-03, 09:28   #4
axn

Jun 2003

123E16 Posts

Quote:
 Originally Posted by NBtarheel_33 I believe (and I might be wrong ) that this is a consequence of the group theory underlying the LL test. Reaching 0 before the final step of an LL test would imply the existence of a nontrivial proper subgroup of a group of prime order, which would contradict Lagrange's Theorem.
So a Mersenne prime can't have this. But most of them are composites. What about them?

 2012-02-03, 10:37 #5 bearnol     Sep 2005 127 Posts Since every factor of a Mersenne number is of the form 2kp+1 [p being the exponent] same reasoning applies for composites, no? J
2012-02-03, 10:39   #6
bearnol

Sep 2005

127 Posts

Quote:
 Originally Posted by bearnol Since every factor of a Mersenne number is of the form 2kp+1 [p being the exponent] same reasoning applies for composites, no? J
Hmmm... possibly not - I think I may be confusing my exponent w/ my number... :)
J

2012-02-03, 10:54   #7
bearnol

Sep 2005

127 Posts

Quote:
 Originally Posted by bearnol Hmmm... possibly not - I think I may be confusing my exponent w/ my number... :) J
Though _maybe_ Fermat's Little Theorem can save my line of reasoning here...
J

2012-02-03, 11:41   #8
NBtarheel_33

"Nathan"
Jul 2008
Maryland, USA

45B16 Posts

Quote:
 Originally Posted by axn So a Mersenne prime can't have this. But most of them are composites. What about them?
But doesn't the group structure come from the exponent p, which we always take to be prime, rather than the number 2^p-1 itself?

 2012-02-03, 12:55 #9 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts If Mp is prime, then it is not possible. We know the order of the group is Mp+1, so is 2^p, and the starting element is chosen to be a non-square in the group, so it likewise has order 2^p. Reaching zero means reaching the element of order 2 sooner than after p-1 squarings, contradicting the above. If Mp is composite, I think it is possible, but exceedingly unlikely. It would require that for each prime factor q of Mp, the order of the starting element in F_q[sqrt(3)] is the same power of 2. It may be possible to construct such composites, for example for P-1 (i.e., not in a quadratic extension), the order of 2 modulo 319489 and 974849 is 4096, so you'd see a residue of -1 (the element of order 2) after 11 squarings. The probability that all prime factors of some Mp are of this kind is practically 0, perhaps provably 0. Last fiddled with by akruppa on 2012-02-03 at 12:57
 2012-02-03, 15:31 #10 CRGreathouse     Aug 2006 10110111011012 Posts Just for kicks I checked: there are no small examples (p < 10^4).
 2012-02-03, 18:02 #11 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40

 Similar Threads Thread Thread Starter Forum Replies Last Post maxal Math 45 2018-12-19 23:32 wildrabbitt Miscellaneous Math 11 2015-03-06 08:17 devarajkandadai Miscellaneous Math 10 2013-08-20 12:57 nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 23:05.

Wed Aug 12 23:05:59 UTC 2020 up 26 days, 18:52, 1 user, load averages: 1.47, 1.36, 1.39