最快素性检验

Question

你能建议一种快速的，确定性的方法，在实践中可用来测试一个大数是否为质数？

另外，我想知道如何正确使用非确定性素数测试。例如，如果我使用这样的方法，如果输出是"no"，我可以确定一个数字不是质数，但当输出是“有可能”时，另一种情况又如何呢？在这种情况下，我必须手动测试素数吗？

提前谢谢。

Answer 1

我所知道的唯一确定的、多项式时间的素性测试算法是AKS素性测试(http://en.wikipedia.org/wiki/AKS_primality_test)。然而，有很多非常好的随机质数测试，它们速度很快，成功的概率也非常高。他们通常通过确定数字是否以指数级的好概率合成来工作，所以他们要么报告数字是合成的，要么要求你非常有把握地说“可能”。

Answer 2

“可能”实际上是指1-ε，而ε会根据你的需要变得尽可能小。

例如，大多数应用程序都有一些与素数测试无关的小而非零的失败概率

• 在密码应用程序中，攻击者幸运地猜测出秘密，例如，2^(-100)
• 硬件故障(辐射引起的)的概率随机翻转计算机内存的某一位(可能保存您的“确定性”素数测试的输出
• bug(实际上，比其他类型的故障更有可能)

因此，将ε按到这个数量级在实践中就足够了。

例如，OpenSSL、GnuPG只使用非确定性素性检验。可能“你并不真的想要确定性测试”。但是，请检查您可以使用的库:如果您手头有任何库，并且它们的性能足够好，那么就继续使用它们。

Answer 3

如果您正在寻找RSA密钥中使用的随机素数，则应该首先使用概率测试。如果概率对于你的需求来说足够高，那么就到此为止。如果你必须确定，那么一旦你找到一个大的随机概率素数，用AKS或另一个非概率测试来验证它。这使您可以快速检查大量非质数，同时确定您认为找到了一个。

如果你试图验证一个特定的现有数是质数，那么你应该使用其中一个肯定回答的测试。还有其他非多项式时间的测试，请使用实践中最快的测试。