
Re: Prime numbers and primality tests
Posted:
Jan 22, 2013 11:18 PM


The original post had this comment: "It is interesting to note, however, that the Lucas pseudo prime method of primality testing apparently does not have the handy "feature" of the MillerRabin test, namely, the provable, and bounded low probability of a wrong answer, from whence an estimate of primality for any number can be made without finding a counter example!"
I just found this interesting article: "The RabinMonier Theorem for Lucas Pseudoprimes", by F. Arnault, in Mathematics of Computation, April, 1997. You can download it from http://www.ams.org/journals/mcom/199766218/S0025571897008363
Theorem 1.3 in that article shows that the probability for each strong Lucas pseudoprime test is 4/15 (analogous to the probability 1/4 for a MillerRabin test).
The key points, though, are these: First, if N is a strong pseudoprime base 2, it is more likely than the average number about that size to also be a strong pseudoprime base 3 (and other bases). So, if you make lists of strong pseudoprimes base 2 and base 3, those lists will overlap, meaning that there are composite numbers that are strong pseudoprimes bases 2 and 3 (and 5, and 7, ...).
Second, if you use any of the algorithms in the "Lucas Pseudoprime" paper at http://mpqs.free.fr/LucasPseudoprimes.pdf to make a list of strong Lucas pseudoprimes, then this list has no known overlap with the list of strong pseudoprimes base 2. It has been checked that any number up to at least 10^16 that passes both types of these strong pseudoprime tests is a prime.
This is why many primetesting functions (e.g, PrimeQ) do at least one of each type of test, instead of just doing standard strong pseudoprime tests to a bunch of different bases 2, 3, ... .

