Fastest primality test

Question

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.

Answer 1

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.

Answer 2

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