On Thursday 21 March 2002 17:58, Naessens Yan wrote: > If a term of the Lucas-Lehmer serie equals 0 modulo Mx, then if it is the > last term Mx is prime else Mx is not prime (because next terms will be -2 ; > 4 ; 4 ; 4...). In both cases, we needn't compute next terms.
This is another recycled thread. Actually the series is 0, -2, +2, +2 , +2, +2 ... There is another very obvious recurrence: +1, -1, -1, -1, -1 ... > Checking if a term of the Lucas-Lehmer serie equals 0 can be done, for > example, during the inverse transform or during the substraction. So, this > test is cheap and it would not slow down the program. A couple of arguments: (1) The probability of any specific residue occurring at any particular iteration (after the first few, and excluding the specific case tested for) is approximately 1 in 2^p-1. Even for small p (~ 1000), this is a _very_ small probability. It's not going to be worth doing the check even if it costs only one CPU clock. (2) If we keep going after p-2 iterations, we may find a zero residue. This would be of considerable value as we would be able to use the information in the iteration count to deduce a factor, in a manner rather similar to the operation of Pollard's rho method. The practical problem is that we would usually have to execute a _very_ large number of iterations... > However, it would be interesting if and only if a term of the Lucas-Lehmer > serie can be 0 before the last term. Or 1. Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
