为什么我执行的 aks prime test 比我执行的 naive 版本慢？

Question

我尝试比较多种算法以找到“i”下的最大质数。但是当我测试实现时，“aks”比我的天真实现慢。我在想 aks 是素数测试的更好实现，我是不是弄错了？

 def expand_x_1(n): 
    c =1
    for i in range(n//2+1):
        c = c*(n-i)//(i+1)
        yield c
 
def aks(p):
    if p==2:
        return True
 
    for i in expand_x_1(p):
        if i % p:
            return False
    return True

def all_factors(x): # naive version
    i = 2
    s = int(x ** 0.5)
    while i < s:
        if x % i == 0:
            return False
        i += 1
    return True

def find(i, func) :
    while not func(i) :
        i -= 1
    print(i)

%time find(2**16, aks)
%time find(2**16, all_factors)

我尝试比较两者并获得：

为 aks

65521
CPU times: user 1.7 s, sys: 3.24 ms, total: 1.7 s
Wall time: 1.7 s

对于all_factor

65521
CPU times: user 81 µs, sys: 0 ns, total: 81 µs
Wall time: 83.9 µs

Answer 1

当输入是素数时，expand_x_1(n) 最终会产生所有可能的 n//2+1 结果，但是 all_factors(n) 中的循环只进行了大约 sqrt(n) 次。那是一个巨大的差异。

但也很有用：

c = c*(n-i)//(i+1)

在迭代中不受限制地增长。添加

            print(c.bit_length())

在 yield 之前，您会看到 find(65521, aks) 在完成之前对超过 65000 位宽的整数进行算术运算。这也比 16 位算术 find(65521, all_factors) 可以。

注意：在实践中，没有人使用 AKS 素数测试，因为即使是经过世界-class 数学家大规模优化的版本也比替代方案慢。有关详细信息，请参阅 AKS Primes algorithm in Python。

为什么我执行的 aks prime test 比我执行的 naive 版本慢？

Why my implementation of aks prime test is slower than my implementation of the naive version?

python

primes

cryptography