20040824, 04:38  #1 
Oct 2003
Australia, Brisbane
2×5×47 Posts 
Rotating the Initial Start Value Of a LL Test
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^71) 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?? 
20040824, 10:11  #2 
Feb 2004
France
3·311 Posts 
nonresidues
Hi,
I don't have the papers with me now, but I think: You can use values A that are nonresidue 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 
20040824, 16:20  #3 
Nov 2003
3·5·11 Posts 
From http://www.mersenne.org/math.htm
GIMPS doublechecking goes a bit further to guard against programming errors. Prior to starting the LucasLehmer test, the S0 value is leftshifted by a random amount. Each squaring just doubles how much we have shifted the S value. Note that the mod 2P1 step merely rotates the pth 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. 
20040824, 23:08  #4 
Oct 2003
Australia, Brisbane
2×5×47 Posts 
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.

20040825, 07:22  #5  
Feb 2004
France
3·311 Posts 
The formula.
I found it.
It's: F(x) = x(x^23) . 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{n1}  U{n2} and 10, 970, 95050, ..., V{n}, ..., where V{n} = 98*V{n1}  V{n2}. Also there are 2^(p2) starting values that depend upon p. For example to test 2^51 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: Quote:
Tony 

20040825, 07:35  #6 
3542_{8} Posts 
LL start
I just posted this in another forum:
A Mersenne number M(p) is prime if M(p) divides S(p2) where S(0)=4 and, S(p)=S(p1)^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^(p1))mod 2^p 1 = 0 [CASE1] L(2^(p1) 1) mod 2^p 1 = 0 [CASE2] Or L(2^(p1) 1)mod 2^p +1 /3 = 0[CASE2] 2^21=3 divides L(2)=3 [C1] 2^31=7 divides, L(4)=7 [C1] 2^51=31 divides, L(15)=1364 [C2] 2^71=127 divides, L(64)=23725150497407 [C1] 2^131=8191 divides, L(4095) [C2] 2^171=131071 divides, L(65535) [C2] 2^191=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^21=3 divides F(4)=3 [C1] 2^31= 7 divides F(8)=21 [C1] 2^51=31 divides F(30)=832040, [C2] 2^71=127 divides F(128)=251728825683549488150424261 [C1] 2^131=8191 divides F(8190) [C2] 2^171=131071 divides F(131070) [C2] 2^191=524287 divides F(524288) [C1] David Broadhurst wrote me: The classic LucasLehmer test for Mersennes uses the Lucas sequence with p=2, q=2, d=p^24*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 twocase test with p=1, q=1, d=p^2q=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. Last fiddled with by TTn on 20040825 at 07:37 
20040825, 07:55  #7 
3·7·137 Posts 
Implicit
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...

20040825, 16:18  #8 
Nov 2003
3×5×11 Posts 
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 nonzero residues if the exponent is not prime. This makes doublechecking useless.

20040825, 17:41  #9 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
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 PariGP code: \\ LL test of 2^p1, initial value shifted left s positions LLshift(p,s) = { local(i, r, t); r = 4 * 2^s % (2^p1); t = s; for (i = 1, p2, t = 2 * t % p; r = (r^2  2 * 2^t) % (2^p1)); return (r * 2^(p  t) % (2^p1)); \\ Shift right t positions } Alex 
20040825, 18:24  #10 
2×3^{2}×11×43 Posts 
TTn
Different track, same train.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Prime95 v28.5.1 Error at Torture test start  RMSe17  Information & Answers  2  20141216 18:55 
How do I start the memory test?  nisko  Information & Answers  5  20130622 05:10 
Can I just start Prime95 by running torture test?  marks9GIMPS  Information & Answers  5  20110605 18:44 
Rotating cylinder  davieddy  Puzzles  7  20080409 01:12 
Making LL test start over  E_tron  Software  2  20040520 13:27 