mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-02-03, 02:23   #1
That Don Guy
 
Feb 2012

2 Posts
Default 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).
That Don Guy is offline   Reply With Quote
Old 2012-02-03, 07:41   #2
ckdo
 
ckdo's Avatar
 
Dec 2007
Cleves, Germany

2·5·53 Posts
Default

Quote:
Originally Posted by That Don Guy View Post
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 View Post
Quote:
Originally Posted by asdf View Post
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.
ckdo is offline   Reply With Quote
Old 2012-02-03, 09:18   #3
NBtarheel_33
 
NBtarheel_33's Avatar
 
"Nathan"
Jul 2008
Maryland, USA

21318 Posts
Default

Quote:
Originally Posted by That Don Guy View Post
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.
NBtarheel_33 is offline   Reply With Quote
Old 2012-02-03, 09:28   #4
axn
 
axn's Avatar
 
Jun 2003

17×281 Posts
Default

Quote:
Originally Posted by NBtarheel_33 View Post
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?
axn is offline   Reply With Quote
Old 2012-02-03, 10:37   #5
bearnol
 
bearnol's Avatar
 
Sep 2005

127 Posts
Default

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 is offline   Reply With Quote
Old 2012-02-03, 10:39   #6
bearnol
 
bearnol's Avatar
 
Sep 2005

127 Posts
Default

Quote:
Originally Posted by bearnol View Post
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 is offline   Reply With Quote
Old 2012-02-03, 10:54   #7
bearnol
 
bearnol's Avatar
 
Sep 2005

1778 Posts
Default

Quote:
Originally Posted by bearnol View Post
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
bearnol is offline   Reply With Quote
Old 2012-02-03, 11:41   #8
NBtarheel_33
 
NBtarheel_33's Avatar
 
"Nathan"
Jul 2008
Maryland, USA

3·7·53 Posts
Default

Quote:
Originally Posted by axn View Post
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?
NBtarheel_33 is offline   Reply With Quote
Old 2012-02-03, 12:55   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25×7×11 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2012-02-03, 15:31   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

Just for kicks I checked: there are no small examples (p < 10^4).
CRGreathouse is offline   Reply With Quote
Old 2012-02-03, 18:02   #11
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts
Default

Well any such test would also have residue of 2, so you could check all verified tests in PrimeNet.
Dubslow is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 13:04.

Wed Nov 25 13:04:21 UTC 2020 up 76 days, 10:15, 4 users, load averages: 1.41, 1.52, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.