c++ - 确定性地检查一个大数是素数还是合数？

Question

我正在寻找一种算法来测试大（如 10 ²⁰⁰）数字。有什么好的算法吗？

理想情况下，我更喜欢不是概率的算法。

注意：数字有超过 50 位且少于 200 位的数字。

Answer 1

如果您正在寻找非概率测试，您可能需要查看AKS primality testing algorithm，它的运行时间大约为 O(log ⁶ n)。对于您拥有的位数，这可能是可行的。

也就是说，概率素性测试非常好，而且许多测试的错误率呈指数级小。我建议使用其中之一，除非有充分的理由不这样做。

编辑：我刚刚发现这个页面包含 AKS 的几个 C++ 实现。我不知道它们是否正常工作，但它们可能是一个很好的起点。

希望这可以帮助！

Answer 2

通常我们会使用可能的主要测试。我推荐BPSW，如果你想要更多的确定性，你可以遵循Frobenius测试和/或一些随机基础的 Miller-Rabin 测试。这将比运行一些证明实现更快并且可以说更确定。

假设你说这还不够好。然后你真的很想使用ECPP并获得证书。合理的实现是Primo或ecpp-dj。这些可以在不到一秒的时间内证明 200 位数字的素数，并返回可以独立验证的证书。

APR-CL是另一种合理的方法。缺点是它不返回证书，因此您信任实现——如果实现正确，您将获得确定性正确的“是”或“否”输出。Pari/GP 使用 APR-CL 及其isprime命令，而 David Cleaver 有一个出色的开源实现：mpz_aprcl。这些实现已经在各种软件中进行了一些代码审查和日常使用，所以应该很好。

AKS是一种在实践中使用的可怕方法。它不返回证书，并且不难找到损坏的实现，这完全违背了首先使用证明方法与良好的可能主要测试的意义。它也非常缓慢。对于我所知道的任何实现，200 位数字都远远超出了实际点。前面提到的 ecpp-dj 软件中包含一个“快速”的软件，因此您可以尝试一下，还有很多其他的实现可以找到。

对于一些速度的想法，这里是一些实现的时间。我不知道任何比所显示的更快的 AKS、APR-CL 或 BPSW 实现（如果您知道，请发表评论）。Primo 开始时比显示的 ecpp-dj 慢一点，但在 500 位左右时它更快，并且有更好的斜率。它是大输入（2,000-30,000 位）的首选程序。