Steinar H. Gunderson wrote: > On Thu, Aug 01, 2002 at 07:01:04AM -0700, Gary Edstrom wrote: > >>I seem to remember reading that there are probabilistic tests that can >>be run on a number. The test is repeated for a number of iterations. >>If the test fails any iteration, then it is definitely NOT prime. If it >>passes a sufficient number of tests, then it is PROBABLY prime. >> >>Now my question is this: "How long does an iteration of one of these >>probabilistic tests take?" and "Can these tests be used on Mersenne >>numbers?" It would seem to be a good way to dispose of even more >>Mersenne candidates before submitting them to the lengthy Lucas-Lehmer >>algorithm. Why isn't it done? > > > Isn't it already done? Prime95 has been doing P-1 tests for quite a while > now. :-) >
Trial factoring and P-1 factoring are not strictly (probabilistic) primality tests. It is true that if they fail to find a factor, the probability that the number under test is prime is increased somewhat as we now know that it contains no small/smooth factors. But this change in probablity is not very great for large numbers as it leaves plenty of possible divisors below the square root of the number. Primality tests like Fermat's test or Miller-Rabin do not tell anything about what the factors of a number might be, but can decide with a high probability whether it is prime or not. Incidentally, Miller-Rabin and Lucas-Lehmer would require the exact same number of squarings, as Mp-1 is 6 (mod 8) (for p>2), so MR would have to exponentiate the base by (Mp-1)/2. This requires p-2 squarings, just like LL. Plus, since all the bits in (Mp-1)/2 are set, MR also needs a multiplication by the base (usually 3) after every squaring, so it would actually be a little slower than LL. Alex _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
