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
