34

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

4

10 回答 10

19

一种好的方法是米勒-拉宾检验。但是应该注意，这只是一个概率测试。

于 2010-04-06T16:47:24.837 回答
18

Jim Sinclair 证明了对七个碱基 2、325、9375、28178、450775、9780504、1795265022 的 Miller-Rabin 测试可以确定性地测试小于 2^64 的数是否为素数。看http://miller-rabin.appspot.com/。

于 2013-08-06T19:16:59.170 回答
10

我相信渐近最快的当前（非概率）素性测试是“Lenstra/Pomerance 改进的 AKS”，它的复杂性基本上是 O(n^6)。

但是，范围long long（假设是 64 位整数的典型系统）并没有那么大。特别是，只有大约 2 亿个小于 2^32 的素数，因此使用快速概率测试，然后使用预先计算的素数列表进行试除（或者只是在素数列表中查找数字，如果你有一个) 在那个范围内会非常快，并且可能是正确的方法。

于 2010-04-06T16:53:45.563 回答
7

我建议使用Miller-Rabin算法的GNU MP 库。我已经用了几个月了，速度非常快。

具体来说，函数 mpz_probab_prime_p 就是这样做的，你也可以使用另一个函数 mpz_nextprime 来查找下一个大于某个数的素数。如果您愿意，我可以发布代码示例。

于 2010-04-06T16:55:59.587 回答
5

如果您想测试 long long 的素数，那么Baillie PSW 素数测试是一个不错的选择。该测试进行了一项强伪素测试和一项卢卡斯测试，因此速度非常快。预计存在一些通过该测试的复合材料，但到目前为止还没有一个已知的，10 15以下当然也不例外。该测试的一个变体例如在 Mathematica 中使用。

于 2010-04-06T21:14:14.737 回答
5

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

等一下——我只需要关上窗户，头顶上全是黑色的直升机........

（或者看看我如何测试素数？）

于 2010-04-06T16:46:58.540 回答
1

Cobbal 和 grokus 是对的。Miller-Rabin 检验是可用算法中最有用的。是的，它是概率性的，但真的不应该吓跑你。该测试是最广泛用于实际目的的测试。

请注意，通过重复测试，可以任意减小误报（没有误报）的概率。

于 2010-04-06T17:00:19.867 回答
1

看看我在这里的回答：

如何测试 1000 位长的素数？

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

于 2010-04-06T17:03:01.480 回答
-1

我认为最好的算法是“ALI primality test”。

于 2013-08-06T18:36:41.987 回答
-3

最快的可能是在预先计算的素数列表中查找它。例如，请参见此处，它们最多有 2^43112609-1（已知的最大素数）。

于 2010-04-06T16:49:02.983 回答