I sent (but didn't see on Math-fun)

Rich once showed me the "Lucas pseudoprime test", of which this may be merely a special case. Let n>2 be not a multiple of 5, phi be the golden ratio, and e:=(-1)^(n^2 mod 5). Then if phi^(n+e) mod n = -e, n is probably prime. Inequality certifies n composite. This presumably follows from ancient lore on the periodicity of the Fibonacci sequence mod n.

The Macsyma function is merely modulus_warn:false$ fibprm(n):=block([modulus:n,e:(-1)^nummod(n^2,5),algebraic:true], is(-ratsimp(%phi^(n+e))=e))

This is fast because RATSIMP exponentiates modulo both n and %phi^2-%phi-1.

Slightly faster is the Maple fibprm:=proc(n) local e; e:=(-1)^(n^2 mod 5); evalb(-e = mods(Powmod(phi,n+e,phi^2-phi-1,phi),n)); end:

The first few pseudoprimes spoofing this test are 4181 = fib(19) = 37 * 113, 5777 = 53 * 109, 6721 = 11 * 13 * 47, 10877 = 73 * 149, . . ., 197209 = 199 * 991, . . ., 1203401 = 401 * 3001, . . ., 1803601 = 601 * 3001, . . ., 1970299 = 199 * 9901 . . ., 4475521 = 211 * 21211, with typical differences gradually increasing, but ratios decreasing. [...]> Erdos (I think) conjectured that in the *very* long run, the density of pseudoprimes will actually increase. There appear to be no even pseudoprimes. This test even rejects 2!

Next after 2^35-6284047 = 34353454321 = 5300641*6481 is the relatively close pair 2^35+28429389 = 34388167757 = 19333 * 1778729 and 2^35+30503233 = 34390241601 = 3 * 89 * 401 * 321203 . Does anyone see what scrutiny of intermediate results might make this test "strong"? --rwg