From: Warren Smith <warren.wds@gmail.com>
Gerhard Jaeschke: On strong pseudoprimes to several bases, Maths. of Comput. 61,204 (1993) 915-926. http://cr.yp.to/bib/1993/jaeschke.pdf
Jaeschke also claims that there are no strong pseudoprimes below 10^12, common to the four prime bases A=2, 13, 23, and 1662803.
Several people have independently looked at pushing those limits. It's been a very long time since I looked at this field, but I think that Jason Moxham was the first to hit several of the limits, but used a slightly stronger combination of tests that Jaeschke did to reduce the number of composites which could slip through, and published his (as usual completely unreadable) code so that his techniques could be verified. A pair (or more) from perhaps China had done similar searches, but used even stronger sets of conditions that further reduced the number of composites that would slip through. They did publish the theoretical basis and findings in an international journal, but didn't supply their code. IIRC, Jason used that quartic character to, where possible, capture the square root of -1. I notice that Jaeschke mentions the quartic character in his paper, but doesn't seem to make use of its value. Any two witnesses to pseudoprimality which provide such a square root must, up to sign, provide the same primitive 4th root of unity. (and if they don't, you've factored the number.) Unfortunately this isn't such a big win as it first seems as you don't always end up with a primitive root. So you only gain when you're already in the cases where many tests are needed. However, when you get the square root you get it for free, so it seems wasteful not to do a simple comparision once you get two of them. Also IIRC, the Chinese pair generalised this to, where they exist, primitive 3rd roots of unity too. This only works when p==1(3), but that's half of the time. Again, you capture the 3rd root, and any two witnesses which provide a primitive one must, up to sign, supply the same one. (ditto re. factoring.) This can be generalised to 5th roots which, up to sign or squaring be identical, but that only aplies to p==1(5). Phil