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 x^2 - x - 1) on page 104 of the first 
edition purports to give the 25 such numbers less than 1E+5, but 
actually lists only 24 numbers.  The missing pseudoprime is 67861.  

Extending the table a bit, there are 86 such pseudoprimes less than 
1E+6.  Of those symmetric pseudorpimes, 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 x^2 - x - 1.

Interestingly, there are quadratics that give a much stronger test for
compositeness.  In particular, the equation x^2 - 4x - 9 has only four
determinate symmetric pseudoprimes less than one million, and only 80
less than 1E+8.  It's also worth noticing that all 80 of these
pseudoprimes masquarade as "splitting primes";  I've never found a
pseudoprime of the "irreducible" type relative to x^2 - 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 1E+8, which covers about half of 
all primes in that range.

One reason that x^2-4x-9 is so much stronger than x^2-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 x^2-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 
x^3-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.,50E+9).

Perrin's polynomial has discriminant -23 and is monic in both 
directions.  Another cubic with the same discriminant is x^3+x^2-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 x^3-9x^2+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  x^4-5x^3-2x^2-3x-1  is the fully symmetric group S_4, 
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  x^5-x^3-2x^2+1  is S_5, and 
the smallest symmetric pseudoprime relative to this quintic is
2258745004684033.  This test can be carried out on an integer N 
using just 15*log_2(N) full-precision multiplications. 

For a more detailed discussion of pseudoprimes based on arbitrary
polynomials, see Symmetric Pseudoprimes.