Mersenne: Another thought on the L-L Test

```Hi,

Another thought struck me - this could have useful applications in L-L
testing programs.```
```
If M is the Mersenne number being tested & R(i) is the L-L residue after i
iterations, then
R(i+1) = R(i) * R(i) - 2 (modulo M) (by the statement of the L-L algorithm)

But note that (M - R(i))^2 - 2 = M^2 - 2MR(i) + R(i)^2 - 2
so (M-R(i))^2 - 2 (modulo M) is clearly equal to R(i+1).

How can this be of any use? Well, when we have a dubious iteration (say an
excessive roundoff or sum error) we can check the output by redoing the last
iteration but starting from (M-R(i)) instead of R(i) - the output should be
the same. Furthermore the action of calculating M-R(i) is very easy - just
invert all the bits.

Also, if we have suspicions about the accuracy of code when there is a high
density of 1 bits, we can try just one iteration but starting at M-4 instead
of 4. The output residual should be 14 irrespective of M (providing M>7 - as
will often be the case!). The point here is that, just as the value 4 is
represented by a string of p bits only one of which is set, M-4 is
represented by a string of p bits only one of which is unset.

Regards
Brian Beesley
_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ      -- http://www.tasam.com/~lrwiman/FAQ-mers
```