On Fri, 15 Jan 1999, Foghorn Leghorn wrote:
> Chris Caldwell's web page on Mersenne numbers descirbes the Lucas-Lehmer
> test briefly and mentions that it is quick on binary computers because
> they can quickly perform division by 2^n-1. I know how to find integer
> quotients and remainders modulo 2^n with shifting and masking, but I
> don't understand how it is done quickly modulo 2^n-1. Would anyone care
> to explain?
The remark was indended to refer to the classical algorithms (with the
right choice of FFT algorithm this step is automatic): the key is that
2^n = 1 (mod 2^n-1), so if we write the number as A*2^n + B (that is, let
B be the last n bits and A the rest, then A*2^n+B = A+B (mod 2^n-1). So
we can reduce with just an addition. For exampe, take the number 23
modulo 7, 23 is (mod 7)
10111 = 10 + 111 = 1001 = 1 + 001 = 10 (mod 111)
Chris.
