python - Python 中的 AKS Primes 算法

Question

几年前，已证明 PRIMES is in P .有没有实现 their primality test 的算法？在 Python 中？我想用一个简单的生成器运行一些基准测试，并亲眼看看它有多快。我会自己实现它，但我对论文的理解还不够。

Answer 1

快速回答:不，AKS 测试不是测试素性的最快方法。有很多很多更快的素性检验，它们要么假设(广义)黎曼假设和/或随机化。 (例如 Miller-Rabin 快速且易于实现。)该论文的真正突破是理论上的，证明存在用于测试素性的确定性多项式时间算法，无需假设 GRH 或其他未经证实的猜想.

也就是说，如果你想理解并实现它，Scott Aaronson's short article可能有帮助。它没有详细介绍所有细节，但您可以从第 10 页(共 12 页)开始，它已经提供了足够的信息。 :-)还有一个list of implementations (主要是 C++)在这里。

此外，对于优化和改进(几个数量级)，您可能需要查看 this report , 或(旧)Crandall and Papadopoulos's report , 或(更旧的)Daniel J Bernstein's report .它们都有相当详细的伪代码，非常适合实现。