I have tweaked the strong fermat pseudoprimality test with two independent and (in retrospect) completely obvious improvements.
For the 419500ish strong base 2 pseudoprimes less than 1e15, one improvement shows that 120936 (28.8%) of them are composite. This improvement requires only a tiny fraction more computation than a normal spsp test.
The second improvement is independent of the first and involves some data which is often generated anyway in the run-up to doing an spsp test. It also has a small additional computational overhead compared to a normal spsp test. This improvement shows that about 45% of the strong base 2 pseudoprimes less than 1e15 are composite.
The canny reader can probably work out what I have done from this post as it's so obvious. In the off-chance that someone hasn't already thought of it, I would dearly like to get a paper (or two!) in Math Comp and I was wondering if I adversely affect my chances of getting it published if I post the method in this forum first.