mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Can LL residue hit zero before the last iteration? (https://www.mersenneforum.org/showthread.php?t=2841)

 JuanTutors 2004-07-31 19:19

Can LL residue hit zero before the last iteration?

Is it known:

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

 jfollas 2004-08-01 12:12

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

 JuanTutors 2004-08-01 18:20

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:

:question: 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?

 jfollas 2004-08-01 19:07

[QUOTE=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?[/QUOTE]
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. :wink:

 All times are UTC. The time now is 03:37.