最快的素性测试
您能否建议一种可在实践中使用的快速、确定性方法来测试大数是否为素数？
另外，我想知道如何正确使用非确定性素性测试。例如，如果我使用这样的方法，如果输出为“否”，我可以确定一个数字不是素数，但是当输出为“可能”时，其他情况又如何呢？在这种情况下我是否必须手动测试素数？
提前致谢。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我所知道的唯一确定性多项式时间素数测试算法是 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.
“可能”实际上意味着 1-ε，并且 ε 可以根据需要变得尽可能小。
大多数应用程序都有一些小但非零的失败概率，与素性测试无关，例如
在加密应用程序中，攻击者幸运地猜测了秘密，例如，
在加密应用中，攻击者幸运地猜到秘密的概率为 2^(-100)
硬件故障（辐射引起的）随机翻转计算机内存的某些位（可能保存“确定性”素性测试的输出
错误（实际上，比其他类型的故障更有可能）
因此，在实践中将 ε 按到这个数量级就足够了，
例如，仅使用非确定性素性测试的 OpenSSL、GnuPG “可能”你并不真正想要。但请检查您可以使用哪些库：如果您手头有任何库，并且它们的性能足够，请继续使用它们。
"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.
如果您正在寻找用于 RSA 密钥的随机素数，您应该首先使用概率测试。如果概率足够高以满足您的需求，那么就到此为止。如果您必须确定，那么一旦您找到一个大的随机概率素数，请使用 AKS 或其他非概率测试来验证它。这可以让您快速检查大量非素数，同时在您认为找到一个时确定。
如果您试图验证特定的现有数字是否为质数，那么您应该使用可以确定答案的测试之一。还有其他非多项式时间测试，请使用实践中最快的测试。
If you're looking to find a random prime for use in RSA keys, you should use a probabilistic test initially. If the probability is high enough for your needs then stop there. If you must be certain, then once you find a large random probable-prime, verify it with AKS or another non-probabilistic test. This lets you check a lot of non-primes quickly while being certain when you think you've found one.
If you're trying to verify a specific existing number is prime then you should use one of the tests that answers with certainty. There are other non-polynomial-time tests too, use the one that is fastest in practice.