Re: Mersenne: Basic question: Working modulo 2^n-1
PS. I forgot vor the v_n approach, the
doubling formula, as used in Mersenne is
v_{2n} = v^2_n - 2 Q^n
and the trippling formula is
v_{3n} = v_n(v^2_n - 3 Q^n ).
Like in the Mersenne Sequences, since only comparison to 0 is required,
one could factor out the Q^n ...
Preda
Mersenne: Basic question: Working modulo 2^n-1
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? __ Get Your Private, Free Email at http://www.hotmail.com
Re: Mersenne: Basic question: Working modulo 2^n-1
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.
