Am I missing something

[LaurV]

@OP:
Yes. You are missing something. Those numbers are wrong. A multiplication with a power of 2 (random shift) will rotate all the operations by that amount, therefore when you square, you double the amount, and when you subtract 2 from the result, that 2 is rotated too, because the result is rotated.

See posts #5, and the following discussion in posts #16, #17, #18, in this thread.

OTOH, if you suggest that starting LL tests with different initial values, instead of the actual** random shift method, would be better (sorry, but as pointed by the former posters, I have no idea what do you want from us with those numbers, so I am trying to guess your mind), then it won't work, because, regardless of the value you start with, after a while the path converges (squaring numbers mod x is not a bijection, all negatives result in positives, so you only have half of the values in the co-domain), therefore FFT will work with the same numbers (or their negatives), which will defeat the goal: to make the FFT deal each time with different data, which would eliminate a bug in the code.

Note that while other measures (GEC test, certification, etc) target hardware errors, cosmic rays, CPU going drunk, user's dishonesty (cheating for credits or whatever reasons), the random shift targets possible errors in software implementation of the FFT (software errors). If the FFT deals with completely different data each time and still produces the same result at the end (shifted or not) then we can be quite confident that the implementation is right.

Ex: 19:
Starts with 10: 10, 98, 9602, 448177, 409322, 200240, 160699, 412414, 313150, 282018, 338709, 353913, 150119, 286038, 129657, 199279, 1024, 0
Starts with 52: 52, 2702, 485071, 160883, 339071, 343957, 7723, 400296, 100378, 519603, 444087, 87082, 511841, 238249, 129657, 199279, 1024, 0

You will note that the last iterations produce the same numbers. Other starting values could produce more or less common iteration (including all of them, for example, if you start with 4 or with -4 (mod Mp), they will coincide from the first). That's not the goal of the random shift.

----------
**former. Since PRP tricks invented by people here, LL is not anymore "actual"

[Nick]

If you are genuinely interested in different starting values (and not just understanding the current implementation),
read Bas Jansen's PhD thesis, available here:
https://scholarlypublications.univer...dle/1887/20310

[Youjaes]

Originally Posted by kriesel

Consider OP, that there may be unclarity or error in your thinking, programming, and communication. As there may be in mine, after having long ago written LL code (without floating point, without shifts) and having read these threads for years and followed prime95's development for decades.

Take it one iteration at a time.
See https://www.mersenneforum.org/showth...818#post572818
Those who've written the major GIMPS software are welcome to comment on that here.

If you like, I can post all the intermediate s values for p=29 and 31 for s0 = 4, 8, and 16. It's not a problem since I'm already calculating the residuals for p<32 with s0 = 4 << (x-2) = 2^x for x = 2..100000. Here are the number of cases out of 99999 where the residual was zero for p<32. Cases for p where the count of zero residues was zero out 99999 were tested but omitted from the list, including p is not Mp and p is not prime.

3, 33333, 33%
5, 20000, 20%
7, 28571, 28%
13, 23077, 23%
17, 23530, 23%
19, 26316, 26%
31, 25806, 25%


For the 99,999 simple cases of s0=x, x= 2.100000 the counts for residues = 0 for the 7 set of Mp's tested are

3, 28572, 28%
5, 25807, 25%
7, 25197, 25%
13, 25007, 25%
17, 24979, 24%
19, 24900, 24%
31, 25025, 25%

My expectation is that for arbitrary starting values of s0, an Mp has a 1 in 4 chance of returning a zero residue and for not Mp, two different starting values have unrelated residues.

Hopefully we'll hear from someone who can shed light on what's happening since frankly, using a start value other than s0=4 is a waste of time. If you can't calculate that residual accurately, the rest isn't worth much

[Dr Sardonicus]

Originally Posted by LaurV

@OP:
Yes. You are missing something. Those numbers are wrong. A multiplication with a power of 2 (random shift) will rotate all the operations by that amount, therefore when you square, you double the amount, and when you subtract 2 from the result, that 2 is rotated too, because the result is rotated.

See posts #5, and the following discussion in posts #16, #17, #18, in this thread.

Ah, the examples tell the tale. When you shift the initial value k bits to the left, it is no longer the constant value 2 being subtracted after each squaring. (This is not mentioned in the given explanation, which only says the initial value is shifted.)

The subtrahend is being systematically shifted, with each iteration. Instead of subtracting the constant value 2 after each squaring starting with 4*2^k, you subtract 2*2^(2*k) after the first squaring, 2*2^(4*k) after the second, 2*2^(8*k) after the third, etc. This is what makes the new sequence of residues merely a shifted version of the original.

[charybdis]

Originally Posted by Youjaes

Hopefully we'll hear from someone who can shed light on what's happening since frankly, using a start value other than s0=4 is a waste of time. If you can't calculate that residual accurately, the rest isn't worth much

Several people have already shed light on what's happening. When we run LL with a shift, we are not just starting with a different power of 2 and iterating x^2-2. We're also shifting the 2 that we subtract at each step. Since squaring doubles the number of bits we shift by, at each iteration we need to double the number of bits that the 2 is shifted by. Kriesel explained this in his post that he linked to.

For example, let's say we shift left by 5 bits, so we start with 2^7 = 128 instead of 2^2 = 4. After the first squaring, the shift doubles to 10 bits, so we need to subtract a 2 shifted left by 10 bits, so 2^11. The unshifted LL gives 4^2-2 = 14, or 1110 in binary. The shifted LL gives 128^2-2^11 = 14336, or 11100000000000 in binary, and this is just 1110 shifted left by 10 bits. At the next iteration the squaring doubles the shift again to 20 bits, so we must subtract 2^21, and so on. Of course we reduce mod 2^p-1 at each step, so we do the same to the power of 2 that we subtract: if p=17, for example, then instead of subtracting 2^21 we subtract 2^4.

Edit: beaten to it, but more examples can only help.

[Youjaes]

Originally Posted by LaurV

@OP:

Note that while other measures (GEC test, certification, etc) target hardware errors, cosmic rays, CPU going drunk, user's dishonesty (cheating for credits or whatever reasons), the random shift targets possible errors in software implementation of the FFT (software errors). If the FFT deals with completely different data each time and still produces the same result at the end (shifted or not) then we can be quite confident that the implementation is right.

Ex: 19:
Starts with 10: 10, 98, 9602, 448177, 409322, 200240, 160699, 412414, 313150, 282018, 338709, 353913, 150119, 286038, 129657, 199279, 1024, 0
Starts with 52: 52, 2702, 485071, 160883, 339071, 343957, 7723, 400296, 100378, 519603, 444087, 87082, 511841, 238249, 129657, 199279, 1024, 0

You chose special starting values known to produce zero residues for known Mp as of 2004. Only one in four arbitrary starting values do that for any particular Mp which I was easily able to calculate with 64-bit ints for p<32 is Mp. For example, starting values of 8,16,32,64, etc. have residues of zero ~25% of the time for the first 100,000 and the first 1,000,000 shifted single bits. Starting values of consecutive integers demonstrates the same pattern for the first 100,000 and 1,000,000 integers.

If the intention is to test the hardware and FFT, wouldn't it be simpler and more efficient to generate p pseudorandom bits, X, and it's conjugate Y = ((2^p - 1) Xor X) = (2^p - 1) - X, i.e. X + Y = X Or Y = 2^p - 1, since (X*X - 2) mod (2^p - 1) = (Y*Y - 2) mod (2^p - 1) and compute a 128-bit Xor checksum on the two values (Xor 128 bit chunks of data at a time together) and if they don't match, do the two multiplications again so that if the error results are the same, then transmit the RNG seed and the two 128-bit checksums because you just found a confirmed error in the math so it's off to see the wizard. If this test were to be performed every 1,000 or 10,000 multiplications during the LL test, then the health of the computing device can be verified independent of the algorithm immediately and you don't have to wait till you are done and not know until someone runs a second LL to find out there is a problem. This way, you don't have to screw around with start values and can always use s0=4 with confidence.

I good RNG can be found on the Wikipedia page for Xorshift.

https://en.wikipedia.org/wiki/Xorshift


James

[charybdis]

Originally Posted by Youjaes

If the intention is to test the hardware and FFT, wouldn't it be simpler and more efficient to generate p pseudorandom bits, X, and it's conjugate Y = ((2^p - 1) Xor X) = (2^p - 1) - X, i.e. X + Y = X Or Y = 2^p - 1, since (X*X - 2) mod (2^p - 1) = (Y*Y - 2) mod (2^p - 1) and compute a 128-bit Xor checksum on the two values (Xor 128 bit chunks of data at a time together) and if they don't match, do the two multiplications again so that if the error results are the same, then transmit the RNG seed and the two 128-bit checksums because you just found a confirmed error in the math so it's off to see the wizard. If this test were to be performed every 1,000 or 10,000 multiplications during the LL test, then the health of the computing device can be verified independent of the algorithm immediately and you don't have to wait till you are done and not know until someone runs a second LL to find out there is a problem. This way, you don't have to screw around with start values and can always use s0=4 with confidence.

1. If I'm understanding you correctly, your idea is to periodically compute X^2 and (N-X)^2 mod N for a random X as a simple hardware check. There are at least two major problems with this. Firstly, your hardware could make errors too rarely to be picked up by your check, but frequently enough to regularly produce incorrect LL residues - say, if it makes an error once in every 100M squarings. Secondly, your check doesn't use any of the actual intermediate values from the LL test, so you could never be totally sure that the test itself contained no errors, even if you ran hundreds of checks for every LL iteration.

2. Using a shift is not "screwing around with start values". It's still using s0=4, but everything is shifted, including the -2. The shift is a separate concept from using an alternative starting value such as 10, which would give a completely different sequence of residues. If we run one test on a composite Mersenne with s0=4 and another with s0=10, we won't get matching residues, so this would not be a suitable method for double-checking (except for primes).

3. As LaurV says, the main intention of the shift is that it will pick up bugs in the FFT implementation: while morally we're performing the same calculations, the numbers that we need to square are bit-shifted, so the FFT computations are different. An FFT bug would therefore produce different incorrect residues with different shifts. Hardware errors are much easier to pick up: even without a shift, they would lead to residues that don't match, if they don't get caught by other means first.

4. GIMPS now prefers to use PRP rather than LL for primality tests, apart from double-checks of LL results. This is because there is a robust error-checking procedure called the Gerbicz error-check which is almost certain to catch any errors during the test. PRP tests can also be certified, allowing a quick verification that the work was done correctly; this means that a double-check is not needed.

[Dr Sardonicus]

Originally Posted by charybdis

<snip>
4. GIMPS now prefers to use PRP rather than LL for primality tests, apart from double-checks of LL results. This is because there is a robust error-checking procedure called the Gerbicz error-check which is almost certain to catch any errors during the test. PRP tests can also be certified, allowing a quick verification that the work was done correctly; this means that a double-check is not needed.

Because of this, apart from double checks on previously LL tested M_p, very few LL tests will be run in future on any M_p, unless it has first tested as a probable prime (i.e. the PRP test fails to prove it composite). If it PRP tests as a probable prime, the result of the LL test will be conclusive. If M_p LL tests as prime, that would be news, because another Mersenne prime would have been found. If an M_p that PRP tests as probable prime then LL tests as composite, that would also be news, because it would be a composite that "fooled" the PRP test.