Re: Mersenne: Algorithm improvements?

[Dave Mullen]

I remember looking at this myself a while back - is this what you meant ?   For a given modulus e.g. M(7) = 127, ignoring the -2 for a while ...   1 ^ 2 = 1 (mod 127) 2 ^ 2 = 4 (mod 127) ... 63 ^ 2 = 32 (mod 127)   and then the results are the same but in reverse order i.e.   64 ^ 2 = 32 (mod 127) ... 125 ^ 2 = 4 (mod 127) 126 ^ 2 = 1 (mod 127)   So effectively, if the MSB of whatever bit length of the exponent you are testing is 1, you could invert the current value before doing the FFT and get the same answer.   But that only saves one bit of calculation, which I don't think makes any difference when the FFT length is rounded up to a power of 2 anyway. So the overhead of inverting the current value only adds to the time taken for an iteration.   With regard to storing arbitrary iteration results and comparing with the current value to detect "loops" - how much time would comparing these numbers take - with my limited number theory, I understood that unless you were lucky and happened to have a prime factor in your test value with a low periodicity, you are very unlikely to hit one of these "loops" anyway.   I think the next true breakthrough on LL testing will only come when someone finds how to do an FFT or other transform without the need to "spread" the 2^N-1 values into a 2^N FFT space (my terminology might be bad, I hope you know what I mean) - and avoid the floating point inaccuracies (and the subsequent required error checking) - anyone done any more reseach on the NTT or similar integer transforms ?   I did have a "play" with NTTs, in an attempt to try and do more that one iteration per forward and reverse transform, but found the difficulty is finding a big enough prime with suitable roots to cope with the magnitude of numbers ^2, never mind ^4 !   Dave