对于2^1024到2^4096范围内的数字，最快的确定性素性测试是什么？

Question

我正在编写一个加密协议的实现。到目前为止，我一直很难找到1024位到4096位整数(308到1233位数字)的最快确定性素性测试。我知道有几种选择，但我还没有找到现实世界中的速度比较。

具体地说，对于这种大小的一般随机数，AKS测试与Rabin-Miller确定性版本和椭圆曲线素性证明测试(以及其他测试)相比表现如何？

Answer 1

本文将回答您的问题：

理查德·P·布伦特的素性测试：http://cs.anu.edu.au/student/comp4600/lectures/comp4600_primality.pdf

它在复杂性和“真实世界的速度”上比较了这3种算法。

Answer 2

我是新来的，所以我不能评论上面的链接，但这是这篇文章的互联网档案链接：

https://web.archive.org/web/20110414142105/http://cs.anu.edu.au/student/comp4600/lectures/comp4600_primality.pdf

Answer 3

对于这种大小，最快的证明方法是APR-CL (例如mpz_aprcl)和ECPP (例如Primo或ecpp-dj)。APR-CL是确定性的，几乎是多项式时间，而ECPP是随机的，但返回的答案是证明的，而不是概率的。或者，对已证实的素数使用构造性方法，如Maurer方法或Shawe-Taylor方法。这些是通过建立Pocklington风格的证明来快速生成随机n比特素数的方法。从实践的角度来看，如果您生成的是随机候选，而不是从第三方接收它们，那么Miller-Rabin的错误率非常低，并且在这种情况下，几乎所有人都对使用随机碱基的多个Miller-Rabin测试感到满意，可能还会使用强大的Lucas测试。有关可能的主要测试的构造方法和建议的大量信息，请参阅FIPS 186-4。

在this graph中显示了通过试除法、BPSW (一种有效的概率素数测试)、两个版本的AKS、APR-CL和ECPP运行的随机n位素数的时间。这显示了AKS与其他方法的比较。

我没有添加确定性M-R，因为我假设你说的不是64位输入，而且你必须要么测试n/4基，要么证明黎曼假设，这样你只需要测试2*log^2(n)基。与我们的其他选择相比，这两个选项都不具吸引力，即使您在没有证明的情况下使用后者。在实践中，巴赫版本比AKS更快，但在我用C+GMP进行的测试中，它比ECPP和APR-CL要慢得多。我没有看过渐近性，但在300位数时，它的速度要慢100倍以上。因此，我看不出与APR-CL (Det M-R更慢)或ECPP (Det M-R更慢，ECPP给你一个证书来引导)相比有什么不同。

布伦特的论文可以在这个UMS10 version from 2010和a similar version from 2006中找到。它基本上与我在C+GMP中发现的各种算法的更现代实现相一致。AKS是一个具有里程碑意义的理论成果，但目前没有实际用途。