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

1328 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

111110 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

10110102 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

2·3·13·41 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

22×3×7×139 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
 
"name field"
Jun 2011
Thailand

24×613 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

2×3×13×41 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

2·32·5 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 20:37.


Fri Dec 3 20:37:36 UTC 2021 up 133 days, 15:06, 0 users, load averages: 1.16, 1.31, 1.22

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.