# Looking for a more efficient primality testing Algorithm than Miller-Rabin

I am looking for a practical probabilistic primality testing algorithm that is more superior than Miller-Rabin. By "more superior", I mean that the probability of giving the wrong answer is better than (1/4)^h where h is the number of times the test is conducted. Any help on this will be highly appreciated.

As Amzoti pointed out, it is much more common to use the BPSW test: a base-2 Miller-Rabin test followed by a strong Lucas test. These are shown to be anti-correlated (that is, pseudoprimes to each test tend to fall in different residue classes, making the intersection much less likely than otherwise). There are no counterexamples under $2^{64}$. There are none known for larger values though we expect them to exist. Further testing can be done if desired (e.g. a base-3 M-R test like Mathematica does, some extra random-base M-R tests like FIPS 186-4 recommends for crypto keys, and/or a Frobenius test).