Python中的AKS Primes算法

几年前，事实证明PRIMES位于P中。是否有任何算法在Python中实现其素数测试？我想用一个幼稚的生成器运行一些基准测试，然后自己看看它有多快。我会自己实现它，但是我对本文的理解还不够。

快速解答：不，AKS测试不是测试素数的最快方法。有太多太多更快素性测试，要么承担（广义）黎曼假设和/或随机化。（例如，Miller-

Rabin快速且易于实现。）该论文的真正突破是理论上的，证明了存在 确定性

多项式时间算法可以测试素数，而无需假设GRH或其他未经证明的猜想。

就是说，如果您想了解和实现它，Scott

Aaronson的简短文章可能会有所帮助。它并没有涉及所有细节，但是您可以从第12页的第10页开始，它已经足够了。:-)这里也有一个实现列表（主要是C

++）。

另外，对于优化和改进（几个数量级），您可能需要查看此报告，或者（较旧的）Crandall和Papadopoulos的报告，或者（较旧的）Daniel

J Bernstein的报告。它们都具有相当详细的伪代码，非常适合实现。