20040731, 19:19  #1 
"Juan Tutors"
Mar 2004
571 Posts 
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<p1? Whether the LL test can zero out before the last step? P.S. Feel free to adjoin your own questions to this thread. 
20040801, 12:12  #2 
Jul 2004
E_{16} Posts 
The LL test will zero out for a prime number Mp on step P1 if the starting term is from the sequence:
A(0)=4, A(1)=52, A(n)=(14*A(n1)  A(n2)) mod Mp [Sloane A018844] It is possible that the LL test will zero out before the P1 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 (P1), followed by a negative two" term (P), followed then by all "two" terms (P+1 to infinity). 
20040801, 18:20  #3 
"Juan Tutors"
Mar 2004
571 Posts 
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? 
20040801, 19:07  #4  
Jul 2004
2×7 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Residue and Shift, what do these mean?  king  Information & Answers  1  20180305 05:52 
Quadratic residue mod 2^p1  alpertron  Miscellaneous Math  17  20120430 15:28 
Residue Number System  flouran  Math  6  20091122 22:50 
Residue classes  CRGreathouse  Math  4  20090312 16:00 
Masked residue  schneelocke  PrimeNet  6  20031122 01:26 