R.Baillie: regarding the last point mentioned below, page 1402 of the baillie-wagstaff "lucas pseudoprimes" paper mentions this: if n is a psp base a, but not a strong psp base a, then we can factor n in the process doing the psp test base a.
This also tells us something that is rather remarkable which I have not seen before: REMARKABLE FACT: Pseudoprimes (i.e. hard cases for our probable-prime test) are easy to factor.
One has to wonder what applications this may have...
--it may be that my observation and the one Baillie points out in his paper (which by the way somebody posted here: http://mpqs.free.fr/LucasPseudoprimes.pdf ) are in some sense the same observation (disguised). I think the underlying reason for these is that if you can find the multiplicative order of some y mod N, i.e. find r so that y^r=1 mod N then it is easy to factor N, i.e. GCD( y^(r/2) +- 1 , N ) will often factor N if r is even, which it is going to be. [If factor is trivial then try another y.] This is just the X^2-1=(X-1)(X+1) trick. For Fermat-style pseudoprimes that keep pretending to be prime, you can figure out the multiplicative order of numerous y mod N so you can factor N. So Carmichael numbers and Fermat pseudoprimes always are easy to factor. Now going to the polynomial world where pseudoprime tests now are based on polynomial(x) powers (mod both a pseudo-irreducible polynomial and mod N)... I suppose we could use the same trick but with polynomial GCD to, for such pseudoprime N, rapidly find polynomial(x) factors of the modulus polynomial, thus proving it really was not irreducible, thus proving N really was not prime. But I am not seeing how to deduce a factor of N itself. I guess this also explains to me a way to make a "strong" version of my "Galois test"... those polynomial GCDs all must be scalars or else we know N composite.