How does the random shift work?

[CuriousKit]

Hi everyone,

So I am trying to work out how the random bit-shift on s₀ works, because I couldn't see how one can derive the final residue correctly from it due to the "- 2" operation.

Taking 2⁷ - 1 as an example, the terms go 4, 14, 47, 42, 111 then s₅0, indicating a prime. If s₀ 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 004₁₀ = 0000 0000 0000 0000 0000 0100₂
0 000 014₁₀ = 0000 0000 0000 0000 0000 1110₂
0 000 194₁₀ = 0000 0000 0000 0000 1100 0010₂
0 037 634₁₀ = 0000 0000 1001 0011 0000 0010₂

So to keep the bit patterns the same (doubling the shift with each iteration):

0 000 008₁₀ = 0000 0000 0000 0000 0000 1000₂ (shl 1)
0 000 056₁₀ = 0000 0000 0000 0000 0011 1000₂ (shl 2 = - 8)
0 003 104₁₀ = 0000 0000 0000 1100 0010 0000₂ (shl 4 = - 32)
9 634 304₁₀ = 1001 0011 0000 0010 0000 0000₂ (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₅.

Now, the subtraction factor grows exponentially large with each step (e.g. for calculating s₅, it is 8,589,934,592, but the laws of modular arithmetic allow you to subtract this value mod 2⁷ - 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.

[TheJudger]

Hi,

the "random shift" isn't completly random, it still has to be a valid initial value.
S₀ = 4 is a universal initial value.

http://www.mersennewiki.org/index.ph..._Values_of_LLT

Oliver

[CuriousKit]

Oh excellent. Thank you.

[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 was wondering the same thing 3.5 years ago:
http://www.mersenneforum.org/showthread.php?t=17014

[ewmayer]

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.

[LaurV]

Originally Posted by TheJudger

Hi,

the "random shift" isn't completly random, it still has to be a valid initial value.
S₀ = 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.

[CuriousKit]

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.

[ATH]

It also makes all double checks more secure as Prime95 works on different data.

[CuriousKit]

Indeed. What I meant was using a different universal value or odd power in "I_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.

[TheJudger]

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.