Is there a Prime number test that has no false positives

Question

The primality tests that I have found, i.e. Fermat and Miller-Rabin don't return any false negatives, but do sometimes return false positives. That is, some composites are incorrectly decided as primes by these algorithms, but primes are always decided as primes.

Is there an efficient (polynomial time in length of the number) primality test that works the other way? That is, it will always correctly decide whether composite numbers are composite, but can sometimes mistake a prime number for a composite number?

Answer 1

The AKS primality test is what you are looking for.

Answer 2

Since primality testing can be done in polynomial time (Primes is in P; Agrawal, Kayal, Saxena; Annals of Mathematics, 2004), there exists an efficient algorithm with neither false negative nor false positive.

Answer 3

Each of these are primality proof methods. They have no false positives. They are not probabilistic tests.

• For small inputs, very fast methods such as BPSW and deterministic Miller-Rabin (verified correct for all 64-bit inputs).

• BLS75 methods, from the 1975 paper. Some of these were known and used hundreds of years ago. The downside is that they rely on partial factoring of either n-1, n+1, or both. Sometimes this is very fast, but for general inputs this eventually becomes performance limited by factoring. Can easily produce a certificate so others can verify the result. Almost certainly not fast enough for general purpose 1024-bit primality testing.

• APR-CL, early 1980s. Quite good in practice and works for numbers of a few thousand digits. It is not polynomial time but for practically computable numbers will have a smaller exponent than AKS. Like AKS, doesn't produce a certificate, so the recipient just has to trust that it's right.

• ECPP, late 1990s. The fastest algorithm for very large inputs in practice. Regularly proves results with 10-30k digits. Randomized polynomial time. Produces a certificate so third parties can quickly validate the primality (e.g. there are 3+ verifiers for Primo style certificates, each written completely independently, so really you're only relying on the actual mathematics in the original papers to be correct).

• AKS, 2002. Deterministic polynomial time for all inputs. Much easier to code than the above, though remarkably full of places to trip up. In practice, much, much slower than APR-CL and ECPP, as expected from their complexity classes No certificate is produced, so you just have to trust the implementation.

In summary, if you're writing an academic paper, just reference AKS as being polynomial time and move on. If you actually want to compute something, use one of the other methods. Particularly APR-CL and ECPP which will be polynomial time in practice with a lower exponent than AKS. Both APR-CL and ECPP, with decent implementations, are usable for current cryptographic sizes, proving 1024-bit primes in under a second, 2048-bit primes in 10-60 seconds.

Pari/GP supports all the methods other than AKS (which as they explain in their FAQ, currently has no practical reason to implement). There are AKS programs for Pari/GP if you insist for some reason, though they are millions of times slower than the others.

I'm harping on AKS because two other answers reference it as the right solution. I think they got really caught up on your mention of polynomial time.

There is another discussion to be had regarding the value of primality proving, especially in the absence of certificates. For instance, I personally estimate the probability that an AKS software implementation has a subtle bug is substantially higher than a simple, good, well-implemented probable prime test (e.g. BPSW plus some extra random Miller-Rabin bases) has let a composite pass through.