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