我知道实际应用中有许多素数测试算法（例如Eratosthenes筛法，Fermat测试，Miller-Rabin算法，AKS等），但它们要么速度较慢（如筛法），要么是概率性的（Fermat和Miller-Rabin），要么相对难以实现（AKS）。
什么是最好的确定性解决方案来确定一个数字是否为质数？
请注意，我主要（双关语意）感兴趣的是针对32位（也许是64位）数量级的数字进行测试。因此，不需要一个适用于更大数字的强大解决方案。
4个回答
11
我能翻译编程相关内容。以下是需要翻译的内容：
在2的30次方以内，您可以使用试除法进行暴力破解。
在3.4*10^14以内，已经证明用前7个质数的Rabin-Miller算法是确定性的。
在此之上，您需要自己解决。目前没有已知的亚立方确定性算法。
编辑：我记得这一点，但直到现在我才找到参考资料：
http://reference.wolfram.com/legacy/v5_2/book/section-A.9.4
PrimeQ首先使用小质数进行可除性测试，然后使用Miller-Rabin强伪素数测试基于2和3，然后使用Lucas测试。
截至1997年，已知此过程仅对
n＜10^16正确，并且可以想象对于更大的n，它可能会声称一个复合数是质数。
因此，如果您实现了Rabin-Miller和Lucas，则可以处理高达10^16的数据。
- Mysticial
10
试除法在我的情况下不可行，因为素性测试会被调用很多次，并且需要尽可能高效。 - tskuzzy
@amit：但正如OP所说，它实现起来很困难。而且它仍然比Rabin-Miller算法慢。 - Mysticial
1@amit：我从未定义“高效”。如果“高效”是指多项式时间复杂度，那么AKS是高效的。但如果“高效”是亚立方级别的，那么AKS就不是高效的。 - Mysticial
1@amit：同意，让我修正我的答案。 - Mysticial
@Mystical：“Rabin-Miller with the first 7 primes”显然是确定性的。非平凡的是，已经证明了使用前7个质数的Rabin-Miller在给定范围内是正确的。 - user380772
显示剩余5条评论
3
如果我不关心空间，我会尝试预计算2^32（约4e9/ln(4e9)*4字节，少于1GB）以下的所有质数，将它们存储在内存中并使用二分查找。您还可以尝试对包含这些预计算质数的文件进行内存映射（优点：程序启动更快，缺点：直到所有所需数据实际上都在内存中之前，速度可能较慢）。
- Alexey Frunze
2
如果你能分解出n-1，那么可以使用19世纪Edouard Lucas开发的一种方法很容易地证明n是质数。你可以在维基百科上阅读算法，或者查看我在我的博客上实现的算法。还有一些只需要部分因式分解的变体算法。
如果n-1的因式分解很困难，最好的方法是椭圆曲线素性证明算法，但这需要更多的数学和代码，可能您不愿意编写。总之，这比AKS要快得多。
你确定你需要一个绝对的质数证明吗？Baillie-Wagstaff算法比任何确定性质数证明器都要快，而且没有已知的反例。
如果您知道 n 永远不会超过 2^64，那么使用 前十二个质数 作为基数的强伪素数测试就足以证明 n 是质数。对于 32 位整数，使用三个基数 2、7 和 61 的强伪素数测试就足以证明其是质数。
如果n-1的因式分解很困难，最好的方法是椭圆曲线素性证明算法，但这需要更多的数学和代码，可能您不愿意编写。总之，这比AKS要快得多。
你确定你需要一个绝对的质数证明吗？Baillie-Wagstaff算法比任何确定性质数证明器都要快，而且没有已知的反例。
如果您知道 n 永远不会超过 2^64，那么使用 前十二个质数 作为基数的强伪素数测试就足以证明 n 是质数。对于 32 位整数，使用三个基数 2、7 和 61 的强伪素数测试就足以证明其是质数。
- user448810
1
使用埃拉托斯特尼筛法预先计算尽可能多的质数，您可以每个数字使用一个位来存储，并通过仅筛选奇数（将2作为特殊情况）来减少一半的空间。
对于从
Sieve.MAX_NUM到Sieve.MAX_NUM的平方的数字，您可以使用试除法，因为您已经列出了所需的质数。在更大的未分解残差上谨慎使用Miller-Rabin测试可以加快进程。对于更大的数字，我会使用其中一种概率测试，Miller-Rabin是很好的选择，如果重复几次，可以得到比计算机硬件故障更不可能出错的结果。
- rossum
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
2^64的质数。32可以。 - Steve Jessop