最快的素数测试

Question

你能推荐一种实际可用的快速确定法，用于判断一个大数是否为质数吗？

另外，我想知道如何正确使用非确定性素性测试。举个例子，如果我正在使用这样的方法，如果输出结果是“否”，我可以确定该数字不是质数，但是如果输出结果是“可能”，那么我需要在这种情况下手动测试质数吗？

提前感谢。

- user500944

---

这个 CS 网站上关于 AKS 质数测试何时更快以及为什么选择哪种方法的问题，其中的答案和评论提供了一些很好的见解。链接如下：https://cs.stackexchange.com/questions/23260/when-is-the-aks-primality-test-actually-faster-than-other-tests - Morten Jensen

Answer 1

我知道的唯一确定性、多项式时间复杂度的素数测试算法是AKS素数测试（http://en.wikipedia.org/wiki/AKS_primality_test）。然而，有很多非常好的随机素数测试，速度快且成功概率极高。它们通常通过指数概率找到数字是否为合数，因此它们要么报告数字是合数，要么需要您以非常高的置信度说“可能是”。

- templatetypedef

---

当我们说“非常自信”时，这是否意味着因系统故障得到错误输出的概率高于算法产生错误答案的概率？ :-) - user500944

@Grigory 这取决于你使用的算法。有些甚至允许你指定概率。测试约为50％，75％，90％等。他所指定的AKS算法，只要编码正确，就可以100％正确回答。 - Mike M.

@Grigory："系统故障"？可能性是涉及其中的，因为“正确”的算法会很慢，所以您可以检查一组更小的值，这将为您提供99.9％的正确答案概率。您认为您使用的“非确定性”术语意味着什么？ - ruslik

@ruslik: 格里戈里基本上是正确的，你可以设置概率素性测试的“置信度”级别，以使得错误判定数为质数的概率如此之低，以至于出现系统故障（例如失败的存储器位或寄存器位）比起素性测试更可能得到错误的阳性结果。 - President James K. Polk

问题要求最有效的算法在实践中可用 - AKS测试在实践中不可用。 - kaya3

Answer 2

“Probably”实际上意味着1-ε，而ε可以尽可能地小。大多数应用程序都有一些小但非零的失败概率，与素性测试无关，例如：在加密应用程序中，攻击者幸运地猜测出密钥，例如，以2^(-100)的概率；硬件故障（辐射引起）随机翻转计算机内存的某个位（也许是保存“确定性”素性测试输出的位）；漏洞（确实比其他类型的故障更有可能）。因此，在实践中，将ε提高到那个数量级就足够了。例如，OpenSSL、GnuPG只使用非确定性素性测试。 “可能”你真的不想要非确定性测试。但是请检查您手头可用的库，并且它们执行得足够好-继续使用它们。

- Mitro

Answer 3

如果您需要寻找随机素数来用于RSA密钥，则应该首先使用概率测试。如果概率足够高以满足您的需求，则可以停止。如果必须要确定，那么一旦您找到一个大的随机可信素数，就请使用AKS或其他非概率性测试进行验证。这样可以快速检查很多非素数，并在您认为已经找到一个素数时保证其准确性。

如果您想要验证一个特定的已知数字是否为素数，那么您应该使用某个可以提供确定性答案的测试方法。还有其他的非多项式时间测试方法，使用实际中最快的那种即可。

- phkahler