mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2016-01-14, 16:58   #1
CuriousKit
 
"J. Gareth Moreton"
Feb 2015
Nomadic

5A16 Posts
Question 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!
CuriousKit is offline   Reply With Quote
Old 2016-01-14, 20:34   #2
TheJudger
 
TheJudger's Avatar
 
"Oliver"
Mar 2005
Germany

100010101112 Posts
Default

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
TheJudger is offline   Reply With Quote
Old 2016-01-14, 20:44   #3
CuriousKit
 
"J. Gareth Moreton"
Feb 2015
Nomadic

2×32×5 Posts
Default

Oh excellent. Thank you.
CuriousKit is offline   Reply With Quote
Old 2016-01-14, 22:06   #4
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3,079 Posts
Default

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
ATH is offline   Reply With Quote
Old 2016-01-15, 02:30   #5
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2·5,813 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
ewmayer is offline   Reply With Quote
Old 2016-01-15, 05:18   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

222478 Posts
Default

Quote:
Originally Posted by TheJudger View Post
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
LaurV is offline   Reply With Quote
Old 2016-01-15, 15:27   #7
CuriousKit
 
"J. Gareth Moreton"
Feb 2015
Nomadic

2×32×5 Posts
Thumbs up

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.
CuriousKit is offline   Reply With Quote
Old 2016-01-15, 17:51   #8
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

60078 Posts
Default

It also makes all double checks more secure as Prime95 works on different data.
ATH is offline   Reply With Quote
Old 2016-01-15, 21:00   #9
CuriousKit
 
"J. Gareth Moreton"
Feb 2015
Nomadic

10110102 Posts
Default

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.
CuriousKit is offline   Reply With Quote
Old 2016-01-16, 00:33   #10
TheJudger
 
TheJudger's Avatar
 
"Oliver"
Mar 2005
Germany

11·101 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
TheJudger is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Residue and Shift, what do these mean? king Information & Answers 1 2018-03-05 05:52
random comments, random questions and thread titles made for Google jasong Lounge 46 2017-05-09 12:32
Alt codes : should shift = +32 in them ? science_man_88 Programming 13 2011-06-24 06:52
Shift Equivalency davar55 Puzzles 3 2009-07-02 19:27
About random number (random seed) in Msieve 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.