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)])
是的,去看看rosettacode.org上的AKS test for primes页面
结果是:
快速回答:不,AKS测试不是最快的测试素性的方法。有许多许多更快的素性检验,要么假设(广义)Riemann假设,要么是随机的。(例如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。它们都有相当详细的伪代码,很适合于实现。
相关问题 更多 >
编程相关推荐