Python 中的 AKS Primes 算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/347811/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
AKS Primes algorithm in Python
提问by Claudiu
A few years ago, it was proven that PRIMES is in P. Are there any algorithms implementing their primality testin Python? I wanted to run some benchmarks with a naive generator and see for myself how fast it is. I'd implement it myself, but I don't understand the paper enough yet to do that.
几年前，已经证明PRIMES 在 P 中。是否有任何算法在 Python 中实现它们的素性测试？我想用一个简单的生成器运行一些基准测试，并亲眼看看它有多快。我会自己实现它，但我对论文的理解还不够充分。
回答by ShreevatsaR
Quick answer: no, the AKS test is not the fastest way to test primality. There are much muchfaster primality tests that either assume the (generalized) Riemann hypothesis and/or are randomized. (E.g. Miller-Rabinis fast and simple to implement.) The real breakthrough of the paper was theoretical, proving that a deterministicpolynomial-time algorithm exists for testing primality, without assuming the GRH or other unproved conjectures.
快速回答：不，AKS 测试不是测试素性的最快方法。有太多太多更快素性测试，要么承担（广义）黎曼假设和/或随机化。（例如，Miller-Rabin 实现起来既快速又简单。）该论文的真正突破是理论上的，证明了存在用于测试素性的确定性多项式时间算法，而无需假设 GRH 或其他未经证实的猜想。
That said, if you want to understand and implement it, Scott Aaronson's short articlemight help. It doesn't go into all the details, but you can start at page 10 of 12, and it gives enough. :-) There is also a list of implementations(mostly in C++) here.
也就是说，如果您想理解和实施它，Scott Aaronson 的短文可能会有所帮助。它没有涉及所有细节，但您可以从第 10 页（共 12 页）开始，它提供了足够的信息。:-) 这里还有一个实现列表（主要是 C++）。
Also, for optimization and improvements (by several orders of magnitude), you might want to look at this report, or (older) Crandall and Papadopoulos's report, or (older still) Daniel J Bernstein's report. All of them have fairly detailed pseudo-code that lends itself well to implementation.
此外，对于优化和改进（几个数量级），您可能需要查看此报告，或（较旧的）Crandall 和 Papadopoulos 的报告，或（较旧的）Daniel J Bernstein 的报告。它们都有相当详细的伪代码，非常适合实现。
回答by Jacques
Yes, go look at AKS test for primespage on rosettacode.org
是的，去rosettacode.org 上查看素数页面的AKS 测试
def expand_x_1(p):
ex = [1]
for i in range(p):
ex.append(ex[-1] * -(p-i) / (i+1))
return ex[::-1]
def aks_test(p):
if p < 2: return False
ex = expand_x_1(p)
ex[0] += 1
return not any(mult % p for mult in ex[0:-1])
print('# p: (x-1)^p for small p')
for p in range(12):
print('%3i: %s' % (p, ' '.join('%+i%s' % (e, ('x^%i' % n) if n else '')
for n,e in enumerate(expand_x_1(p)))))
print('\n# small primes using the aks test')
print([p for p in range(101) if aks_test(p)])
and the output is:
输出是：
# p: (x-1)^p for small p
0: +1
1: -1 +1x^1
2: +1 -2x^1 +1x^2
3: -1 +3x^1 -3x^2 +1x^3
4: +1 -4x^1 +6x^2 -4x^3 +1x^4
5: -1 +5x^1 -10x^2 +10x^3 -5x^4 +1x^5
6: +1 -6x^1 +15x^2 -20x^3 +15x^4 -6x^5 +1x^6
7: -1 +7x^1 -21x^2 +35x^3 -35x^4 +21x^5 -7x^6 +1x^7
8: +1 -8x^1 +28x^2 -56x^3 +70x^4 -56x^5 +28x^6 -8x^7 +1x^8
9: -1 +9x^1 -36x^2 +84x^3 -126x^4 +126x^5 -84x^6 +36x^7 -9x^8 +1x^9
10: +1 -10x^1 +45x^2 -120x^3 +210x^4 -252x^5 +210x^6 -120x^7 +45x^8 -10x^9 +1x^10
11: -1 +11x^1 -55x^2 +165x^3 -330x^4 +462x^5 -462x^6 +330x^7 -165x^8 +55x^9 -11x^10 +1x^11
# small primes using the aks test
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
