|
Lucas and Perrin Pseudoprimes |
|
|
|
Lucas pseudoprimes are discussed in Ribenboim's "The Book of Prime Number Records" (Springer, 1988), along with the algebraic identities that can be used to compute the nth Lucas number in O(log(n)) steps. Incidentally, the table of Lucas pseudoprimes (of the second kind, corresponding to the quadratic x2 − x − 1) on page 104 of the first edition purports to give the 25 such numbers less than 105, but actually lists only 24 numbers. The missing pseudoprime is 67861. |
|
|
|
Extending the table a bit, there are 86 such pseudoprimes less than 106. Of those symmetric pseudoprimes, 19 can be excluded because they are not determinate (eleven being divisible by the discriminant, and eighteen having 1 < gcd[N,b0(N)] < N). Eleven of the remaining pseudoprimes can be excluded because they have the wrong Jacobi symbol, so this leaves just 56 composites less than a million that cannot be distinguished from primes based on the quadratic x2 − x − 1. |
|
|
|
Interestingly, there are quadratics that give a much stronger test for compositeness. In particular, the equation x2 − 4x − 9 has only four determinate symmetric pseudoprimes less than one million, and only 80 less than 108. It's also worth noticing that all 80 of these pseudoprimes masquerade as "splitting primes"; I've never found a pseudoprime of the "irreducible" type relative to x2 − 4x − 9 (although I assume they exist). It follows that this test is both necessary and sufficient for establishing the primality of any "irreducible" integer less than 108, which covers about half of all primes in that range. |
|
|
|
One reason that x2 − 4x − 9 is so much stronger than x2 − x − 1 is that my definition of a symmetric pseudoprime requires that any symmetric function of the Nth powers of the roots must be congruent to the same function of the 1st powers. This implies that, in general, a quadratic pseudoprime test imposes two congruence conditions (corresponding to the two elementary symmetric functions of the roots). However, the Fibonacci polynomial is degenerate because it is "monic in both directions", so it imposes only one congruence condition. (Many authors try to strengthen the x2 − x − 1 test by defining congruence conditions on both the Lucas sequence and the Fibonacci sequence, but that approach does not generalize well to higher degrees.) |
|
|
|
Even stronger tests are given by higher degree polynomials. For example, Shanks and Adams found the composite number 27664033, which in my terms is the smallest symmetric pseudoprime relative to x3 − x − 1. (They called this "Perrin's polynomial" because Perrin wrote a brief note on the corresponding sequence in the 1890's; however, Lucas had already given a much better treatment (better than Perrin, not better than Shanks and Adams) in his 1876 paper.) There are 55 symmetric pseudoprimes less than 50 billion (i.e., 50∙109). |
|
|
|
Perrin's polynomial has discriminant -23 and is monic in both directions. Another cubic with the same discriminant is x3 + x2 − 4x – 5. There are only four numbers less than 50 billion that are symmetric pseudoprimes relative to this polynomial and Perrin's polynomial, and all four are Carmichael numbers. |
|
|
|
To show that's there's nothing particularly good about discriminant -23, the cubic x3 − 9x2 + 24x – 15 has discriminant -135, and the smallest symmetric pseudoprime (equal to the product of two splitting primes) relative to this polynomial is 196049701. |
|
|
|
Generally, the larger the group of a polynomial, the stronger is the primality test based on that polynomial. The group of quartic polynomial x4 − 5x3 − 2x2 − 3x – 1 is the fully symmetric group S4, and the smallest symmetric pseudoprime (equal to the product of two splitting primes) relative to this polynomial is 12282695011. Even better, the group of the quintic x5 – x3 − 2x2 + 1 is S5, and the smallest symmetric pseudoprime relative to this quintic is 2258745004684033. This test can be carried out on an integer N using just 15 log2(N) full-precision multiplications. |
|
|
|
For a more detailed discussion of pseudoprimes based on arbitrary polynomials, see Symmetric Pseudoprimes. |
|
|