mersenneforum.org  

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

Closed Thread
 
Thread Tools
Old 2004-07-31, 19:19   #1
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

22F16 Posts
Default Can LL residue hit zero before the last iteration?

Is it known:

Whether the LL test can loop? That is, can S(j) = S(k) for some 0<j<k<p-1?
Whether the LL test can zero out before the last step?

P.S. Feel free to adjoin your own questions to this thread.
JuanTutors is offline  
Old 2004-08-01, 12:12   #2
jfollas
 
Jul 2004

11102 Posts
Default

The LL test will zero out for a prime number Mp on step P-1 if the starting term is from the sequence:

A(0)=4, A(1)=52, A(n)=(14*A(n-1) - A(n-2)) mod Mp [Sloane A018844]

It is possible that the LL test will zero out before the P-1 step if a starting term other than what's provided by the sequence above is used. For instance, say you started with 194 (the 3rd natural term if you start with 4). Then you can expect two less steps will be required in order to reach the primality conclusion.

Note also that some LL test programs (glucas comes to mind, but I'm not sure about Prime95) check to see if you have a zero term (or a two term) before the expected end of test, and if so, declares the test a failure at that point. These programs also randomly shift the starting term of "4" so that two different runs of the LL test can be performed at the same time, which should produce the same end result. However, in the slim chance that one of these shifts turns out to be a natural intermediate term, then you're going to reach a premature end of the LL test from an iterative viewpoint (because you would in fact be starting somewhere in the middle).

If the LL sequence begins to loop using a starting term from the sequence above, then the Mersenne being tested is not prime. IOW, the LL sequence modulo a prime Mersenne will contain unique terms all the way to the zero term (P-1), followed by a negative two" term (P), followed then by all "two" terms (P+1 to infinity).
jfollas is offline  
Old 2004-08-01, 18:20   #3
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

13·43 Posts
Default

Thanks jfollas. I actually didn't know about that "random shift" they do. I don't think I was clear enough when I asked my questions, though...

I meant to ask the questions referring to the test unmodified using other tricks like starting from the 3rd term in the sequence or modifying the start value in a way that just helps to verify that the test was run correctly, etc. From what I understand, this "random shift" is just a trick used to help verify the result, and that this "shift" doesn't usually bring S(1)=4 to one of the valid STARTING values of the sequence (like to S(1) = 10 or the other valid starting values depending on the prime being tested).

If you start the test right from the beginning, from S(1) = 4 or 10 or one of the other valid STARTING values of the sequence, i.e. S(1) but not S(2) or S(3), etc, assuming a perfect computer with infinite and infallible accuracy (or, say, an omnipotent God) can the test ever go into a loop or zero out before the end of the test? Is this even known?

Another (arbitrarily hard) one:

Supposing the test can go into loop or zero out before the end of the test, is it true that the test will do so with any/every valid starting value?
JuanTutors is offline  
Old 2004-08-01, 19:07   #4
jfollas
 
Jul 2004

2·7 Posts
Default

Quote:
Originally Posted by dominicanpapi82
If you start the test right from the beginning, from S(1) = 4 or 10 or one of the other valid STARTING values of the sequence, i.e. S(1) but not S(2) or S(3), etc, assuming a perfect computer with infinite and infallible accuracy (or, say, an omnipotent God) can the test ever go into a loop or zero out before the end of the test? Is this even known?
I've studied the Lucas-Lehmer sequence quite a bit over the past year, and based on all of the empirical evidence that I've collected, I have concluded that the LL sequence will zero out after any number of terms only for prime modulii, and furthermore, initiating the sequence with a "natural start" of 4, will zero out only on the P-1 term. Of course, I would welcome a contradiction so I can finally put this Lemma to bed.
jfollas is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Residue and Shift, what do these mean? king Information & Answers 1 2018-03-05 05:52
Quadratic residue mod 2^p-1 alpertron Miscellaneous Math 17 2012-04-30 15:28
Residue Number System flouran Math 6 2009-11-22 22:50
Residue classes CRGreathouse Math 4 2009-03-12 16:00
Masked residue schneelocke PrimeNet 6 2003-11-22 01:26

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


Tue Dec 7 05:41:35 UTC 2021 up 137 days, 10 mins, 0 users, load averages: 1.75, 1.55, 1.59

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.