gpt4 book ai didi

python - Python 中的 AKS Primes 算法

转载 作者:IT老高 更新时间:2023-10-28 21:51:51 25 4
gpt4 key购买 nike

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

最佳答案

快速回答:不,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 .它们都有相当详细的伪代码,非常适合实现。

关于python - Python 中的 AKS Primes 算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/347811/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com