小数的简单确定性素性检验

Question

我知道在实践中有许多素性测试算法( Eratosthenes筛法，Fermat's test，Miller-Rabin，AKS等)。然而，它们要么很慢(例如sieve)，要么是概率论的(Fermat和Miller-Rabin)，要么相对难以实现(AKS)。

确定一个数是否为素数的最佳确定性解决方案是什么？

请注意，我主要(双关语)感兴趣的是针对32位(也可能是64位)的数字进行测试。因此，不需要健壮的解决方案(适用于更大的数字)。

Answer 1

到了~2^30，你就可以用审判部门来暴力破解了。

一直到3.4*10^14，Rabin-Miller with the first 7 primes has been proven to be deterministic。

除此之外，你得靠你自己。目前还没有已知的亚立方确定性算法。

编辑:我记得这一点，但直到现在我才找到引用：

http://reference.wolfram.com/legacy/v5_2/book/section-A.9.4

PrimeQ首先使用小素数测试可除性，然后使用米勒-拉宾强伪素数测试基数2和基数3，然后使用卢卡斯测试。

截至1997年，已知此过程仅适用于n < 10^16，并且可以想象，对于较大的n，它可以声称一个合成数是质数。

所以如果你实现了拉宾-米勒和卢卡斯，你可以达到10^16。

Answer 2

如果我不关心空间，我会尝试预先计算2^32 (~4e9/ln(4e9)*4字节，小于1 1GB)以下的所有素数，将它们存储在内存中并使用二进制搜索。你也可以使用包含这些预计算素数的文件的内存映射(优点:更快的程序启动，缺点:在所有需要的数据实际在内存中之前会很慢)。

Answer 3

如果你能因数n-1，就很容易证明n是素数，这是由爱德华·卢卡斯在19世纪开发的一种方法。您可以在Wikipedia上阅读该算法，或者在my blog上查看我的算法实现。该算法的一些变体只需要部分因子分解。

如果n-1的因式分解很困难，最好的方法是elliptic curve primality proving算法，但这需要比您愿意编写的更多的数学和代码。在任何情况下，这都比AKS快得多。

你确定你需要一个质数的绝对证明吗？Baillie-Wagstaff algorithm比任何确定性质数证明器都要快，而且没有已知的反例。

如果您知道n永远不会超过2^64，那么使用first twelve primes作为基数的强伪素数测试足以证明n素数。对于32位整数，对3个基数2、7和61的强伪素数测试足以证明素性。