C++ 素性测试的最快算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2586596/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fastest algorithm for primality test
提问by dada
I need to test primality on intervals between numbers which are really big (in the range of long long), so i need some fast algorithm for checking if a number is prime or not. Please suggest your ideas.
我需要测试非常大的数字之间的间隔（在 long long 范围内）的素性，所以我需要一些快速算法来检查一个数字是否是素数。请提出你的想法。
回答by cobbal
One good method is the Miller-Rabintest. It should be noted however, that this is only a probabilistic test.
一种很好的方法是Miller-Rabin测试。然而，应该注意的是，这只是一个概率测试。
回答by user448810
A Miller-Rabin test to the seven bases 2, 325, 9375, 28178, 450775, 9780504, 1795265022 has been proved by Jim Sinclair to deterministically test if a number less than 2^64 is prime. See http://miller-rabin.appspot.com/.
Jim Sinclair 已证明对 7 个基数 2、325、9375、28178、450775、9780504、1795265022 的 Miller-Rabin 检验可以确定性地检验小于 2^64 的数是否为质数。看http://miller-rabin.appspot.com/。
回答by Stephen Canon
I believe that the asymptotically fastest current (non-probabilistic) primality test is the "Lenstra/Pomerance improved AKS", which has complexity that is essentially O(n^6).
我相信渐近最快的当前（非概率）素性测试是“Lenstra/Pomerance 改进的 AKS”，它的复杂性基本上是 O(n^6)。
However, the range of long long(assuming a typical system where that is a 64 bit integer) is not really that big. In particular, there are only ~200 million primes less than 2^32, so using a fast probabilistic test, followed by trial division with a precomputed list of primes (or just looking the number up in a list of primes, if you have one) would be pretty darn fast in that range, and is probably the right way to go about it.
然而，long long（假设一个典型的系统是一个 64 位整数）的范围并不是那么大。特别是，只有大约 2 亿个小于 2^32 的素数，所以使用快速概率测试，然后用预先计算的素数列表进行试除（或者只是在素数列表中查找数字，如果你有一个) 在那个范围内会非常快，并且可能是正确的方法。
回答by grokus
I would suggest the GNU MP librarythat uses the Miller-Rabinalgorithm. I have used it for a few months and it's very fast.
我会建议使用Miller-Rabin算法的GNU MP 库。我已经使用它几个月了，它非常快。
Specifically, the function mpz_probab_prime_p does this, you can also use another function mpz_nextprime to find the next prime number greater than a number. I can post code samples if you would like.
具体来说，函数 mpz_probab_prime_p 就是这样做的，你也可以使用另一个函数 mpz_nextprime 来查找下一个大于某个数的素数。如果您愿意，我可以发布代码示例。
回答by Martin Beckett
I came up with a really good algorithm, that is much faster than checking all the divisors - which of course also lets me crack public key encryption.
我想出了一个非常好的算法，它比检查所有除数要快得多——这当然也让我破解公钥加密。
Hang on - I just need to close the window, there are all these black helicopters overhead ........
坚持住 - 我只需要关上窗户，头顶上全是黑色直升机........
(Or look at How can I test for primality?)
（或者看看如何测试素数？）
回答by Accipitridae
If you want to test a long long for primality then the Baillie PSW primality testis a good choice. This test does one strong pseudoprime test and one Lucas test and hence is very fast. It is expected that there exist some composites that pass this test, but so far none are known, and there certainly is no exception below 1015. A variant of this test is for example used in Mathematica.
如果您想测试长长的素性，那么Baillie PSW 素性测试是一个不错的选择。这个测试做了一个强伪素数测试和一个 Lucas 测试，因此速度非常快。预计会有一些复合材料通过这个测试，但目前还没有一个是已知的，10 15以下当然也不例外。例如，该测试的一个变体在 Mathematica 中使用。
回答by Rob Lachlan
Cobbal and grokus are right. The Miller-Rabin test is the most useful of the available algorithms. Yes, it is probabilistic, but really shouldn't scare you off. The test is the most widely used for practical purposes.
Cobbal 和 Grokus 是对的。Miller-Rabin 测试是可用算法中最有用的一种。是的，这是概率性的，但真的不应该把你吓跑。该测试是最广泛用于实际目的的测试。
Note that the probability of false positives (there are no false negatives) can be made arbitrarily small by repeating the test.
请注意，通过重复测试可以任意减小误报（没有漏报）的概率。
回答by Sam Harwell
Take a look at my answer here:
在这里看看我的回答：
how to test a prime number 1000 digits long?
The test is very fast. If you are working in the 64-bit or smaller range, you can throw in a GCD with 30030 to save a bit of time for the majority of numbers.
测试速度非常快。如果您在 64 位或更小的范围内工作，则可以使用 30030 加入 GCD 以节省大部分时间。
回答by Yousef
The best algorithm best of my view is "ALI primality test".
我认为最好的算法是“ALI 素性测试”。
回答by JRL
Fastest would probably be to look it up in a precomputed list of primes. See here for example, they have up to 2^43112609-1 (largest known prime).
