Rotating the Initial Start Value Of a LL Test

[dave_0273]

I am not really sure if this is the right forum, so if it isn't feel free to move it...


I am wondering how the rotating of the initial start value of a LL test works. What I assume that it means is that instead of using S(0)=4 you start with another value.

I tried this on M7 (2^7-1) which is prime. I started with 5, but that didn't give a result of 0. So, I tested some other numbers up to 20. I found the following....

S(0)=3,4,10,18 gave a residue of 0, however the rest of the numbers between 1 and 20 did not.

However, seeing as the residue should be 0 no matter how much you rotate it (or at least that is what I assume), I must be doing something wrong.

Is someone able to point me on the right track please??

[T.Rex]

Hi,
I don't have the papers with me now, but I think:
You can use values A that are non-residue modulo Mq (that means there is no x such that x^2 - 2 ~= A (mod Mq)). Like 4 and 52 .
There are 2 formula for finding these numbers starting from 4. I don't remember them now ...
Example: q=5 Mq=31 , you can use 4, 9, 10 and 11 (and -4, -9, -10, -11) as starting values for A.
52 = 31 + 21 ~= -10 (mod 31) .
I'll give more info later.
Tony

[nfortino]

From http://www.mersenne.org/math.htm

GIMPS double-checking goes a bit further to guard against programming errors. Prior to starting the Lucas-Lehmer test, the S0 value is left-shifted by a random amount. Each squaring just doubles how much we have shifted the S value. Note that the mod 2P-1 step merely rotates the p-th bits and above to the least significant bits, so there is no loss of information. Why do we go to this trouble? If there were a bug in the FFT code, then the shifting of the S values ensures that the FFTs in the first primality test are dealing with completely different data than the FFTs in the second primality test. It would be near impossible for a programming bug to produce the same final 64 bit residues.

[dave_0273]

T.Rex, if you could get those 2 formulas to me for how to generate the initial values of an LL test, that would be really appreciated.

[T.Rex]

I found it.

It's: F(x) = x(x^2-3) .
If you compute: x=F(x) (mod Mq) for q=5 and starting with x=4, you get: 4, -10, -9, 11, -4, 10, 9, -11, and 4 again.
Notice that: f(F(x)) = F(f(x)) !!! I think this is very important, but I have no proof and I found no information about it. It's just experimental. I call F the orthogonal function to f.

The other formula are:
"For starting values we can use 4, 52, 724, ..., U{n}, ..., where U{n} = 14*U{n-1} - U{n-2} and 10, 970, 95050, ..., V{n}, ..., where V{n} = 98*V{n-1} - V{n-2}. Also there are 2^(p-2) starting values that depend upon p. For example to test 2^5-1 we could use the starting values 4, 9, 10, 11, 20, 21, 22, or 27."
98 = 14*7 (why ??).
But I don't have the theory explaining that.

Meaning that:

f(x) = x^2-2 <==> U{n} =14*U{n-1} - U{n-2}
F(x) = x(x^2-3) <==> V{n} = 98*V{n-1} - V{n-2}

Regards,
Tony

I just posted this in another forum:

A Mersenne number M(p) is prime if M(p) divides S(p-2) where S(0)=4
and, S(p)=S(p-1)^2 -2(mod 2^p -1)
With S(0)=3, you get my double case test/probable test, where L(n)
are Lucas numbers, via the golden proportion)(10/19/01)
The golden ratio could possibly speed up the squarings involved.
Since there are various algorithmic ways to generate Lucas numbers, by adding fractals etc.
The mod here, would be subracted at each add, rather than divided out.

L(2^(p-1))mod 2^p -1 = 0 [CASE1]
L(2^(p-1) -1) mod 2^p -1 = 0 [CASE2]
Or L(2^(p-1) -1)mod 2^p +1 /3 = 0[CASE2]

2^2-1=3 divides L(2)=3 [C1]
2^3-1=7 divides, L(4)=7 [C1]
2^5-1=31 divides, L(15)=1364 [C2]
2^7-1=127 divides, L(64)=23725150497407 [C1]
2^13-1=8191 divides, L(4095) [C2]
2^17-1=131071 divides, L(65535) [C2]
2^19-1=524287 divides, L(262144) [C1]

So, also with F(n): (Fibonacci numbers)
F(2^p) mod 2^p -1 = 0[Case 1]
F(2^p -2) mod 2^p -1 = 0[Case 2]
Or F(2^p -2) mod 2^p +1 /3 = 0[Case 2]


2^2-1=3 divides F(4)=3 [C1]
2^3-1= 7 divides F(8)=21 [C1]
2^5-1=31 divides F(30)=832040, [C2]
2^7-1=127 divides F(128)=251728825683549488150424261 [C1]
2^13-1=8191 divides F(8190) [C2]
2^17-1=131071 divides F(131070) [C2]
2^19-1=524287 divides F(524288) [C1]


David Broadhurst wrote me:
The classic Lucas-Lehmer test for Mersennes
uses the Lucas sequence with
p=2, q=-2, d=p^2-4*q=12 (Ribenboim p.92).
You can "probably" use the same batch of theorems
from Ribenboim to prove the necessity and sufficiency
of your more complicated two-case test with
p=1, q=-1, d=p^2-q=5 (i.e. the rabbit case).

This is proven completey true up to Lucas# = L(2^4499)
Though, the residue of the Mersenne exponent mod 4, decides whether
or not the test is deterministic.

Though this test should never be wrong, otherwise a zeta zero would fall outside the critical strip. I have no proof of this, I just believe...

[nfortino]

While the multiple roots of the LL test are very interesting, they are not the answer to Dave's original question (or at least I don't think so). I assume he was asking about how the rotation of the start value is used by prime95. Prime95 left shifts (i.e. multiplies by a power of 2) by a random amount. It is possible to trace the effect of this left shift throughout the test, and undo it at the end, giving the final residue. Using a different root of the LL test cannot be used because it affects the residue in an unpredictable way. While all roots will return 0 if the exponent is prime, they return different non-zero residues if the exponent is not prime. This makes double-checking useless.

[akruppa]

Re. Dave's original question:

the subtraction of 2 must be shifted, too. In each iteration, the position of the unit bit doubles (mod p), due to the squaring.

i.e.

(r * 2^s)^2 - 2 * 2^(2s) = (r^2 - 2) * 2^(2s)

Example Pari-GP code:

\\ LL test of 2^p-1, initial value shifted left s positions
LLshift(p,s) =
{
local(i, r, t);
r = 4 * 2^s % (2^p-1);
t = s;
for (i = 1, p-2, t = 2 * t % p; r = (r^2 - 2 * 2^t) % (2^p-1));
return (r * 2^(p - t) % (2^p-1)); \\ Shift right t positions
}


Alex

Different track, same train.