Fastest primality test

Could you suggest a fast, deterministic method that is usable in practice, for testing if a large number is prime or not?

Also, I would like to know how to use non-deterministic primality tests correctly. For example, if I'm using such a method, I can be sure that a number is not prime if the output is "no", but what about the other case, when the output is "probably"? Do I have to test for primality manually in this case?

Thanks in advance.

The only deterministic, polynomial-time algorithm for primality testing I know of is the AKS primality test (http://en.wikipedia.org/wiki/AKS_primality_test). However, there are a lot of very good randomized primality tests that are fast and have extremely good probability of success. They usually work by finding whether the number is composite with exponentially good probability, so they'll either report that the number is composite or will require you to say "maybe" with very good confidence.

"Probably" actually means 1-ε, and ε gets as small as you need.

Most applications have some small yet nonzero probability of failing that is not connected to primality testing, for example

• in cryptographic applications, an attacker luckily guessing the secret with, for example, a probability of 2^(-100)

• a hardware failure (radiation-induced) randomly flipping some bit of your computer memory (maybe one that holds the output of your "deterministic" primality test

• bugs (indeed, more probable than the other type of failures)

So pressing the ε to that order of magnitude will suffice in practice.

For example, OpenSSL, GnuPG of use non-deterministic primality test only. ``Probably'' you don't really want no deterministic test. But check what is available to you: If you have any libraries at hand, and they perform enough - go on and use them.

If you're looking to find a random prime for use in RSA keys, you should use a probabilistic test initially. If the probability is high enough for your needs then stop there. If you must be certain, then once you find a large random probable-prime, verify it with AKS or another non-probabilistic test. This lets you check a lot of non-primes quickly while being certain when you think you've found one.

If you're trying to verify a specific existing number is prime then you should use one of the tests that answers with certainty. There are other non-polynomial-time tests too, use the one that is fastest in practice.