Python中的AKS素数算法

Question

几年前，有人证明了 素数问题可以在多项式时间内解决。有没有人用Python实现过 他们的素数测试算法？我想用一个简单的生成器来跑一下测试，看看它到底有多快。我想自己实现一下，但我对那篇论文还不够了解，没办法做到。

Answer 1

是的，去看看 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)])

输出结果是：

# 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]

Answer 2

我用二项式展开法简化了这个问题。

from math import comb
                                
def AKS(n):
    if (n ^ 1 == n + 1):        # check if it's even
        if n == 2:
            return True         
        return False
    for i in range(3,n//2):
        if comb(n,i)%n != 0:    # check if any coefficient isn't divisible by n
            return False
    return True

Answer 3

简单来说，AKS测试并不是检测一个数是否是质数的最快方法。其实还有很多更快的质数检测方法，这些方法要么假设了（广义的）黎曼假设，要么是随机的。比如，米勒-拉宾测试就很快，而且实现起来也简单。本文的真正突破在于理论上证明了存在一种确定性的多项式时间算法，可以用来检测质数，而不需要假设GRH或其他未被证明的猜想。

不过，如果你想理解并实现这个算法，Scott Aaronson的短文可能会对你有帮助。虽然它没有详细讲解所有内容，但你可以从第10页开始阅读，内容足够让你入门。:-) 这里还有一个实现列表（大部分是用C++写的）。

另外，如果你想进行优化和改进（可以提升几个数量级），可以看看这份报告，或者（更早的）Crandall和Papadopoulos的报告，还有（更早的）Daniel J Bernstein的报告。这些报告都有相当详细的伪代码，适合用来实现。