你能提供一个快速的，确定性的方法在实践中使用，用于测试是否大量是素数或不？

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?

在此先感谢。

推荐答案

唯一的确定性，多项式时间算法素性测试我所知道的是AKS素性测试（的 http://en.wikipedia.org/wiki/AKS_primality_test ）。不过，也有很多很好的随机素性测试，速度快且有成功的非常好的概率。他们通常通过查找号码是否与复合指数好概率工作，所以他们就会要么报告的数量是复合还是会要求你说也许，具有非常好的信心。

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.