1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

The strong Lucas test has a bound of 4/15. The extra strong Lucas test has a bound of 1/8. These don't have "bases" however, so you can't run them multiple times, and the cost is close to 2x a M-R test. The Quadratic Frobenius test has a bound of 1/7710 while taking in theory about 3x the cost. There are also the MQFT and EQFT tests based on the QFT.

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).

If you really want other tests, the fast Frobenius test of Paul Underwood could be useful (it's a fast way of combining a Fermat and Lucas test, without overlapping the BPSW tests). It doesn't have proven error bounds. The Perrin test has very few pseudoprimes, but is relatively expensive and I don't know that anyone has shown error bounds for it.

One thing to additionally consider is the bases used. If M-R testing is used with a fixed set (e.g. the first N prime bases) or deterministic set (e.g. the pseudorandom set used by GMP), then counterexamples can be constructed which will fail every time. Hence for those numbers, the probability of error is 100%. Using actual random bases prevents this, but makes testing and error reproduction more difficult.

$\endgroup$
1
$\begingroup$

Grantham's Frobenius pseudoprimality test has far less error probability per round than a Miller-Rabin round. It requires somewhat more effort per round, but it seems that this is more than compensated by the smaller error margin.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.