Can zero be an "intermediate step" value in Lucas-Lehmer?

That Don Guy · 2012-02-03, 02:23

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).

ckdo · 2012-02-03, 07:41

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.

NBtarheel_33 · 2012-02-03, 09:18

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.

axn · 2012-02-03, 09:28

Quote:

Originally Posted by NBtarheel_33

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.

So a Mersenne prime can't have this. But most of them are composites. What about them?

bearnol · 2012-02-03, 10:37

Since every factor of a Mersenne number is of the form 2kp+1 [p being the exponent] same reasoning applies for composites, no?
J

bearnol · 2012-02-03, 10:39

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

bearnol · 2012-02-03, 10:54

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

NBtarheel_33 · 2012-02-03, 11:41

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?

akruppa · 2012-02-03, 12:55

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.

CRGreathouse · 2012-02-03, 15:31

Just for kicks I checked: there are no small examples (p < 10^4).

Dubslow · 2012-02-03, 18:02

Well any such test would also have residue of 2, so you could check all verified tests in PrimeNet.

2012-02-03, 02:23	#1
That Don Guy Feb 2012 2₁₀ 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, 12:55	#9
akruppa "Nancy" Aug 2002 Alexandria 9A3₁₆ 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Penultimate Lucas-Lehmer step	maxal	Math	45	2018-12-19 23:32
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!"	wildrabbitt	Miscellaneous Math	11	2015-03-06 08:17
"one step backward _two steps forward "	devarajkandadai	Miscellaneous Math	10	2013-08-20 12:57
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?	nitai1999	Software	7	2004-08-26 18:12

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, 15:31	#10
CRGreathouse Aug 2006 3×1,993 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<A<43 -89<O<-88 7221₁₀ Posts	Well any such test would also have residue of 2, so you could check all verified tests in PrimeNet.