Python中的AKS Primes算法

Question

几年前,证明了PRIMES在P中.是否有任何算法在Python中实现其素性测试？我想用一个天真的生成器运行一些基准测试,看看它有多快.我自己实现它,但是我还没有足够的理解这篇论文.

Answer 1

快速回答:不,AKS测试不是测试素数的最快方法.有太多太多更快素性测试,要么承担(广义)黎曼假设和/或随机化.(例如,Miller-Rabin实现快速且简单.)本文的真正突破是理论上的,证明了存在一个确定性多项式时间算法来测试素数,而不假设GRH或其他未经证实的猜想.

也就是说,如果你想理解并实现它,Scott Aaronson的简短文章可能有所帮助.它没有详细介绍所有细节,但你可以从12页的第10页开始,它就足够了.:-)这里还有一个实现列表(主要是在C++中).

此外,为了进行优化和改进(几个数量级),您可能需要查看此报告,或者(较旧的)Crandall和Papadopoulos的报告,或者(较旧的)Daniel J Bernstein的报告.所有这些都具有相当详细的伪代码,非常适合实现.

更新:Terence Tao对数学的另一个很好的阐述:http://terrytao.wordpress.com/2009/08/11/the-aks-primality-test/ (2认同)
@Progo：更准确地说，这是我们可以“证明”的第一个测试是傻瓜式的和多项式时间的。我们坚信还有其他测试*实际上*绝对是万无一失的（例如，因为有可能假设他们假设像黎曼假说这样的强烈猜想来证明它们），还有其他一些测试我们可以*证明*是完美的防呆，并且几乎总是运行很快，但是我们不能*证明*是多项式时间。AKS的突破是同时做到的。 (2认同)