Return to Revisions

While there is no known counterexample to the assumption that the probabilistic Baillie–PSW primality test is actually a proper primality test, there is strong evidence that there exist such counterexamples. -- In 1984, Carl Pomerance has even given a heuristic argument (see here) that for any $\epsilon > 0$ and large enough $x$, the number of composites $\leq x$ failing the test is larger than $x^{1-\epsilon}$ -- yet none is known so far.