mersenneforum.org > Math How does the random shift work?
 Register FAQ Search Today's Posts Mark Forums Read

 2016-01-14, 16:58 #1 CuriousKit   "J. Gareth Moreton" Feb 2015 Nomadic 5A16 Posts How does the random shift work? Hi everyone, So I am trying to work out how the random bit-shift on s0 works, because I couldn't see how one can derive the final residue correctly from it due to the "- 2" operation. Taking 27 - 1 as an example, the terms go 4, 14, 47, 42, 111 then s50, indicating a prime. If s0 is left-shifted 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 bit-shifting 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 Lucas-Lehmer sequence are: 0 000 00410 = 0000 0000 0000 0000 0000 01002 0 000 01410 = 0000 0000 0000 0000 0000 11102 0 000 19410 = 0000 0000 0000 0000 1100 00102 0 037 63410 = 0000 0000 1001 0011 0000 00102 So to keep the bit patterns the same (doubling the shift with each iteration): 0 000 00810 = 0000 0000 0000 0000 0000 10002 (shl 1) 0 000 05610 = 0000 0000 0000 0000 0011 10002 (shl 2 = - 8) 0 003 10410 = 0000 0000 0000 1100 0010 00002 (shl 4 = - 32) 9 634 30410 = 1001 0011 0000 0010 0000 00002 (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 s5. Now, the subtraction factor grows exponentially large with each step (e.g. for calculating s5, it is 8,589,934,592, but the laws of modular arithmetic allow you to subtract this value mod 27 - 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 non-zero. Last fiddled with by CuriousKit on 2016-01-14 at 16:59 Reason: Well I got SOMETHING at least!
 2016-01-14, 20:34 #2 TheJudger     "Oliver" Mar 2005 Germany 100010101112 Posts Hi, the "random shift" isn't completly random, it still has to be a valid initial value. S0 = 4 is a universal initial value. http://www.mersennewiki.org/index.ph..._Values_of_LLT Oliver
 2016-01-14, 20:44 #3 CuriousKit   "J. Gareth Moreton" Feb 2015 Nomadic 2×32×5 Posts Oh excellent. Thank you.
 2016-01-14, 22:06 #4 ATH Einyen     Dec 2003 Denmark 3,079 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
2016-01-15, 02:30   #5
ewmayer
2ω=0

Sep 2002
República de California

2·5,813 Posts

Quote:
 Originally Posted by ATH 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'm sure you know this but to avoid confusing any n00bs) That glosses over the intermediate steps - more precise is:

1. In LL-testing 2^p-1, we shift the initial seed (any of the valid LL-test 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^p-1 has just p bits).

2. On each of the ensuing (p-2) LL-test iterations, we double the current-iteration shift count: s_n = 2*s_{n-1} (modulo p).

3. If on iteration n (initial seed has n = 0) we are writing an interim residue to a savefile for purposes of restart-after-interrupt 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) on-the-fly in the case of a restart-from-interrupt;
[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 shift-count chain, or we can simply select a fresh random shift in [0,p-1] to rotate the r read from the savefile by before continuing the LL test.

3. After the final LL iteration (n = p-2), we simply unrotate (or more accurately, rightward-rotate) the final residue by the final shift count to get r = r'>>s_n.

Note that in practical-implementation 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 subtract-2 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 variable-word-size aspect of the Crandall/Fagin IBDWT used for modern LL testing: For example, say we are testing 2^61-1 for primality using a length-4 FFT and thus words 0-3 having sizes 16,15,15,15 bits, respectively, following the standard IBDWT wordsize formula. If our current-iteration 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)<<(47-46) = -4 to the carry propagated from word 2 into word 3.

2016-01-15, 05:18   #6
LaurV
Romulan Interpreter

Jun 2011
Thailand

222478 Posts

Quote:
 Originally Posted by TheJudger Hi, the "random shift" isn't completly random, it still has to be a valid initial value. S0 = 4 is a universal initial value. http://www.mersennewiki.org/index.ph..._Values_of_LLT Oliver
The random shift is completely random. You confuse it with the start value.

@CuriousKit: see here, and all posts to about post 20 in that thread.

Last fiddled with by LaurV on 2016-01-15 at 05:24

 2016-01-15, 15:27 #7 CuriousKit   "J. Gareth Moreton" Feb 2015 Nomadic 2×32×5 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.
 2016-01-15, 17:51 #8 ATH Einyen     Dec 2003 Denmark 60078 Posts It also makes all double checks more secure as Prime95 works on different data.
 2016-01-15, 21:00 #9 CuriousKit   "J. Gareth Moreton" Feb 2015 Nomadic 10110102 Posts Indeed. What I meant was using a different universal value or odd power in "In = ω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.
2016-01-16, 00:33   #10
TheJudger

"Oliver"
Mar 2005
Germany

11·101 Posts

Quote:
 Originally Posted by LaurV The random shift is completely random. You confuse it with the start value.
Yep, you're right, I have interchanged the options somehow, sorry.

Last fiddled with by TheJudger on 2016-01-16 at 00:34

 Similar Threads Thread Thread Starter Forum Replies Last Post king Information & Answers 1 2018-03-05 05:52 jasong Lounge 46 2017-05-09 12:32 science_man_88 Programming 13 2011-06-24 06:52 davar55 Puzzles 3 2009-07-02 19:27 Greenk12 Factoring 1 2008-11-15 13:56

All times are UTC. The time now is 08:50.

Wed Apr 21 08:50:32 UTC 2021 up 13 days, 3:31, 0 users, load averages: 2.68, 2.96, 2.94