我正在编写一个加密协议的实现。到目前为止，我一直很难找到1024位到4096位整数（308到1233位数字）的最快确定性素性测试。我知道有几个选择，但我没能找到现实世界中的速度比较。
具体来说，对于这种大小的一般随机数，与拉宾·米勒的确定性版本和椭圆曲线素数证明测试（以及其他测试）相比，AKS测试的表现如何？
本文回答您的问题：
Richard p.Brent的初步测试：http://cs.anu.edu.au/student/comp4600/lectures/comp4600_primality.pdf
它比较了这三种算法的复杂性和"真实世界的速度"。
我是新来的，所以我不能对上面的链接发表评论，但这是这篇文章的互联网档案链接：
https://web.archive.org/web/20110414142105/http://cs.anu.edu.au/student/comp4600/lectures/comp4600_primality.pdf
对于这种大小，最快的证明方法是APR-CL（例如mpz_aprcl）和ECPP（例如Primo或ECPP-dj）。APR-CL是确定性的，几乎是多项式时间，而ECPP是随机的，但返回的答案是证明的，而不是概率的。或者，对已证明的素数使用构造性方法，如Maurer方法或Shawe Taylor方法。这些是通过建立Pocklington风格的证明来快速生成随机n位素数的方法。从实践的角度来看，如果你生成随机候选者，而不是从第三方接收它们，那么Miller Rabin的错误率非常低，在这种情况下，几乎所有人都对使用随机基的多个Miller Rabin测试感到满意，可能还有一个强Lucas测试。请参阅FIPS 186-4，了解关于可能的初步测试的构造方法和建议的大量信息。
该图显示了通过试划分、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会给你一个启动证书）相比有任何区别。
布伦特的论文可以在2010年的UMS10版本以及2006年的类似版本中找到。它基本上与我在C+GMP中更现代的各种算法实现中发现的一致。AKS是一个具有里程碑意义的理论成果，但目前没有实际用途。