algorithm - 小数字的简单确定性素数测试

Question

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

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

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

Answer 1

最多~2^30你可以用审判 split 来蛮力。

最多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 first tests for divisibility using small primes, then uses the Miller-Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test.

As of 1997, this procedure is known to be correct only for n < 10^16, and it is conceivable that for larger n it could claim a composite number to be prime.

因此，如果您实现 Rabin-Miller 和 Lucas，您可以达到 10^16。