Here:
https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test
an effective prime-test is mentioned that apparently does not have a small counterexample.
Here :
http://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html
an argument that the smallest counterexample should have at least $10^4$ digits is mentioned but it does not convince me.
I have several questions about this test :
- Has the range upto $2^{64}$ been double-checked ?
- Is it expected that infinite many counterexamples exist ?
How large is the smallest counterexample be expected ? Is there a good chance that it must be hundreds of digits long, or do we only have intuitive guesses ?
Do we know effective necessary conditions for a counter-example that allow to rule out most of the numbers to be a counter-example ?