为什么AKS在实践中这么慢？

Question

本说明(http://maths-people.anu.edu.au/~brent/pd/primality4.pdf)指出，AKS是不实用的。然而，众所周知，AKS是在多项式时间运行的，我不知道AKS算法的慢度是从哪里来的？Brent，在上面的链接上，证明了在算法计算过程中硬件错误的高概率是正确的。有人可以解释布雷特的理由，或者解释我的其他缺点吗？

Answer 1

下面是Brent在幻灯片上担心的硬件错误问题(我不是说我同意，我只是说问题所在)：

假设我们运行了我们的算法，它给出了一个“它是素数”的结果；我们如何确定该算法在运行该算法时没有因为内部硬件错误而给出错误的答案？这听起来可能是一个微不足道的点，因为实际硬件上的错误概率实际上很小。然而，我们没有运行Miller-Rabin的100次迭代的全部原因是我们想要确定；我们是否确定我们没有在AKS中遇到一个内部错误，就像米勒·拉宾( Miller Rabin )的100次迭代(对于任何合理的输入大小都比AKS快得多)一样？

好的，AKS只是输出一个答案"Prime“或"Not”；如果您想验证结果，我们没有比再次运行AKS更好的方法了。

相反，考虑替代算法椭圆曲线素数证明或ECPP。这个算法也总是回答“素”或“非素”，而且总是正确的。然而，它也会生成一个“原始证书”；这个原始证书可以用一个单独的快速算法重新检查。复合数字不存在这样的素数证书；因此，一旦我们运行了ECPP (并生成了一个证书)，如果在ECPP期间遇到硬件错误就不那么重要了；如果原始证书验证了，则该数字必须是素数(即使ECPP确实有硬件错误)。

以上是问题的答案，这里是另一个要考虑的问题。

实际上，ECPP比AKS快得多。因此，除非有人发现AKS有进一步的进步(并降低了它的指数)，否则几乎没有理由实际使用AKS；如果您坚持使用可证明素数，则使用ECPP；如果概率方法足够好，则使用Miller-Rabin (或类似的算法)；或者，如果您正在搜索素数，则可以考虑构造素数的可证明方法(如Shawe-Taylor)。

那么，如果AKS在实践中没有用，为什么人们对它如此感兴趣呢？嗯，虽然ECPP更快，但它实际上是一个拉斯维加斯算法；它是随机的，但是，与Miller-Rabin不同，它永远不会返回错误的答案；相反，它的低概率失效模式是它可能会继续运行。相反，AKS是一种确定性多项式时间算法。