logo标签列表

最快的素数测试算法

c++algorithmmathprimes
34

我需要在非常大的数字区间（long long范围内）上测试素数，因此我需要一些快速的算法来检查一个数字是否为素数。请提出你的想法。

你只需要检查它是否为质数，还是需要找出它的质因数？ - Stephen Canon
质因数分解很困难。这就是RSA加密的基础。虽然你没有回答Stephen的问题，所以我假设你只是想测试一个数字是否为质数。 - ldog
重复的问题 https://dev59.com/ZHRB5IYBdhLWcg3wbGtB - Martin Beckett
你是否需要确定它是质数还是只满足于有很高的正确概率？ - David Thornley
4
这个问题似乎与数论无关，建议前往math.stackexchange.com提问。 - jww
10个回答
19
4
在广义黎曼假设的假设下，Miller-Rabin 测试可以被改进为确定性测试。由于广义黎曼假设被广泛认为是成立的，因此我可以想象一种情况，你可以将该测试用作已经被证明为确定性的测试，因为它是迄今为止最快的。 - Mark Lavin
3
@Mark：针对指定的输入范围，我们不需要假设广义黎曼猜想成立，我们仅需要一个较弱的假设，即确定性的 Miller-Rabin 算法在 LONGLONG_MAX 以下没有误判。这可能更容易证明，尽管我仍然不愿意尝试通过穷举测试来证明它。 - Steve Jessop
18

Jim Sinclair证明了Miller-Rabin测试对于基数2、325、9375、28178、450775、9780504、1795265022可以确定地测试小于2^64的数字是否为质数。请参阅http://miller-rabin.appspot.com/。

10

我认为目前（非概率）素数测试中渐进最快的是“Lenstra / Pomerance改进的AKS”，其复杂度基本上是O(n^6)。

然而，long long的范围（假设典型系统为64位整数）并不是很大。特别是，在小于2^32的范围内只有约两亿个质数，因此在该范围内使用快速概率测试，再用预先计算好的质数列表进行试除运算（或者如果你有质数列表，直接在列表中查找数字），将会非常快，并且可能是正确的方法。

1
在进行概率测试后，您无需进行试除法。如果您运行n次概率测试，则错误答案的概率为1/2^n，因此如果n = 100，则算法将在10^30次中出现1次错误。最好只是运行更多次的概率测试而不是进行试除法。 - theycallhimtom
9
特别是在真实硬件上，由于异常强烈的宇宙射线或其他偶发的硬件故障导致寄存器值翻转，概率测试失败的概率很快就不比确定性测试失败的概率更高。 - Steve Jessop
8
我建议使用使用GNU MP库，它使用Miller-Rabin算法。我已经使用了几个月，速度非常快。
具体来说，函数mpz_probab_prime_p可以实现此功能，您还可以使用另一个函数mpz_nextprime来查找大于某个数字的下一个质数。如果您需要，我可以发布代码示例。
6

我想出了一个非常好的算法，比检查所有除数要快得多 - 当然这也让我破解了公钥加密。

等等 - 我只需要关闭窗口，因为上面有所有这些黑色直升机........

(或者查看如何测试质数？)

6
分解合数（这是破解RSA所需的）与仅测试一个数字是否为质数不同（后者不一定需要寻找任何特定因子）。实际上，实现RSA需要找到具有数百位数的质数，使用简单的“检查所有潜在除数”的算法将是不可行的。 - sth
是的，但如果有更快的测试质数的方法，你就不会在这里告诉任何人了;-) 不管怎样，这个问题都将被关闭为重复。 - Martin Beckett
5

如果您想测试一个长整型数是否为质数，那么Baillie PSW质性测试是一个不错的选择。这个测试只需要进行一次强伪素数测试和一次Lucas测试，因此速度非常快。预计有一些组合数可以通过此测试，但迄今为止没有已知的例外，且在1015以下肯定不存在。例如，Mathematica中使用了这个测试的变体。

1
Cobbal和grokus是正确的。Miller-Rabin测试是可用算法中最有用的。是的，它是概率性的，但实际上不应该吓到你。该测试在实际应用中被广泛使用。
请注意，通过重复测试，假阳性（没有假阴性）的概率可以被任意减小。
1

请看我在这里的答案：

如何测试一千位数的质数？

这个测试非常快速。如果您正在64位或更小的范围内工作，则可以使用30030的GCD来为大多数数字节省一点时间。

-1

在我看来，最好的算法是“ALI素性测试”。

-3

最快的方法可能是在预先计算好的质数列表中查找。例如，请参见此处，他们拥有高达2^43112609-1（已知最大质数）。

3
这个方法行不通。没有电脑能够存储如此长的列表。根据对pi(2^64)的粗略估计，即使没有进行压缩，这个列表所需的存储空间将超过十亿吉字节。 - Dietrich Epp
2
@Dietrich：但是楼主不需要那么多。 - UncleBens
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接