20160114, 16:58  #1 
"J. Gareth Moreton"
Feb 2015
Nomadic
90_{10} Posts 
How does the random shift work?
Hi everyone,
So I am trying to work out how the random bitshift on s_{0} works, because I couldn't see how one can derive the final residue correctly from it due to the " 2" operation. Taking 2^{7}  1 as an example, the terms go 4, 14, 47, 42, 111 then s_{5}0, indicating a prime. If s_{0} is leftshifted by 1 so it starts at 8, then the sequence is 8, 62, 32, 6, 34 then 11, which is certainly not correct. Next I tried bitshifting the subtraction operation by the same amount (so it is " 4")  that produced 8, 60, 40, 72, 100 then 90, and " 8" produced 8, 56, 80, 42, 105 then 95. Finally, analysing the bit patterns directly, I tried changing the subtraction factor each step. Without the mod factor, the first four terms of the LucasLehmer sequence are: 0 000 004_{10} = 0000 0000 0000 0000 0000 0100_{2} 0 000 014_{10} = 0000 0000 0000 0000 0000 1110_{2} 0 000 194_{10} = 0000 0000 0000 0000 1100 0010_{2} 0 037 634_{10} = 0000 0000 1001 0011 0000 0010_{2} So to keep the bit patterns the same (doubling the shift with each iteration): 0 000 008_{10} = 0000 0000 0000 0000 0000 1000_{2} (shl 1) 0 000 056_{10} = 0000 0000 0000 0000 0011 1000_{2} (shl 2 =  8) 0 003 104_{10} = 0000 0000 0000 1100 0010 0000_{2} (shl 4 =  32) 9 634 304_{10} = 1001 0011 0000 0010 0000 0000_{2} (shl 8 =  512) So if I'm right in thinking, you have to double the shift on the  2 factor each time for it to work, right (at least for an initial left shift of 1)? I was thrown initially because this produces the values 8, 56, 56... and I stopped there briefly, thinking it was in a loop... but calculating further after remembering the changing subtraction term... 84, 63, then the expected 0 at s_{5}. Now, the subtraction factor grows exponentially large with each step (e.g. for calculating s_{5}, it is 8,589,934,592, but the laws of modular arithmetic allow you to subtract this value mod 2^{7}  1 to produce the same final result, which in this case is simply 32 (for M7, the subtraction factors are 8, 32, 4, 8, 32 in that order) Am I on the right line of thinking? Of course, I still need to work out how to derive the correct residue at the end if it is nonzero. Last fiddled with by CuriousKit on 20160114 at 16:59 Reason: Well I got SOMETHING at least! 
20160114, 20:34  #2 
"Oliver"
Mar 2005
Germany
11·101 Posts 
Hi,
the "random shift" isn't completly random, it still has to be a valid initial value. S_{0} = 4 is a universal initial value. http://www.mersennewiki.org/index.ph..._Values_of_LLT Oliver 
20160114, 20:44  #3 
"J. Gareth Moreton"
Feb 2015
Nomadic
132_{8} Posts 
Oh excellent. Thank you.

20160114, 22:06  #4 
Einyen
Dec 2003
Denmark
3,313 Posts 
Actually Prime95 always uses S0=4 but then shift it a random amount which is then shifted back for the final (and interim) residue.
I was wondering the same thing 3.5 years ago: http://www.mersenneforum.org/showthread.php?t=17014 
20160115, 02:30  #5  
∂^{2}ω=0
Sep 2002
República de California
2DCF_{16} Posts 
Quote:
1. In LLtesting 2^p1, we shift the initial seed (any of the valid LLtest starting value, but 4 is most common) leftward by s_0 bits, where the initial shift s_0 is a randomly selected nonnegative integer < p (since 2^p1 has just p bits). 2. On each of the ensuing (p2) LLtest iterations, we double the currentiteration shift count: s_n = 2*s_{n1} (modulo p). 3. If on iteration n (initial seed has n = 0) we are writing an interim residue to a savefile for purposes of restartafterinterrupt capability, we need to either [a] write the current value of s to the savefile along with the rotated residue r' = r<<s_n; [b] write the starting value of s to the savefile along with the rotated residue r' = r<<s_n, then compute s_n = 2^n*s_0 (mod p) onthefly in the case of a restartfrominterrupt; [c] write the unrotated residue r to the savefile. In this latter case we can either do as in [a] or [b] and any restart will continue the same shiftcount chain, or we can simply select a fresh random shift in [0,p1] to rotate the r read from the savefile by before continuing the LL test. 3. After the final LL iteration (n = p2), we simply unrotate (or more accurately, rightwardrotate) the final residue by the final shift count to get r = r'>>s_n. Note that in practicalimplementation terms the scheme does complicate things in the normalize, round and carry step at the end of each LL iteration, because instead of simply effecting the subtract2 by initing the carry to 2, we need to figure out into which word of the multiword residue array to 'inject' the (shifted) 2. This is further complicated by the variablewordsize aspect of the Crandall/Fagin IBDWT used for modern LL testing: For example, say we are testing 2^611 for primality using a length4 FFT and thus words 03 having sizes 16,15,15,15 bits, respectively, following the standard IBDWT wordsize formula. If our currentiteration shift count = 47 (say), we need to insert (2)<<47 into the carry chain. Since the bit counts of the first 3 words add up to 46 we need to add (2)<<(4746) = 4 to the carry propagated from word 2 into word 3. 

20160115, 05:18  #6  
Romulan Interpreter
"name field"
Jun 2011
Thailand
3^{5}·41 Posts 
Quote:
@CuriousKit: see here, and all posts to about post 20 in that thread. Last fiddled with by LaurV on 20160115 at 05:24 

20160115, 15:27  #7 
"J. Gareth Moreton"
Feb 2015
Nomadic
1011010_{2} Posts 
Cheers LaurV. I managed to find it myself after traversing all the links and posts. Some very useful information there.
Presumably, using a different start value is only practical (in the context of GIMPS) for verifying a potential prime. 
20160115, 17:51  #8 
Einyen
Dec 2003
Denmark
3,313 Posts 
It also makes all double checks more secure as Prime95 works on different data.

20160115, 21:00  #9 
"J. Gareth Moreton"
Feb 2015
Nomadic
2·3^{2}·5 Posts 
Indeed. What I meant was using a different universal value or odd power in "I_{n} = ω^{n} + ϖ^{n}", where "ω = 2 + √3" and "ϖ = 2  √3" if the universal value used is 4, and "ω = 5 + 2√6" and "ϖ = 5  2√6" if the universal value used is 10.

20160116, 00:33  #10 
"Oliver"
Mar 2005
Germany
11×101 Posts 
Yep, you're right, I have interchanged the options somehow, sorry.
Last fiddled with by TheJudger on 20160116 at 00:34 
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 
random comments, random questions and thread titles made for Google  jasong  Lounge  46  20170509 12:32 
Alt codes : should shift = +32 in them ?  science_man_88  Programming  13  20110624 06:52 
Shift Equivalency  davar55  Puzzles  3  20090702 19:27 
About random number (random seed) in Msieve  Greenk12  Factoring  1  20081115 13:56 