View Single Post
Old 2021-03-02, 06:15   #12
Romulan Interpreter
LaurV's Avatar
"name field"
Jun 2011

1024510 Posts

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"

Last fiddled with by LaurV on 2021-03-02 at 06:36
LaurV is offline   Reply With Quote