Numpy AKS 素数函数

Question

我正在使用 Numpy 实施 AKS-primality 测试。具体来说，我使用 Numpy 的多项式功能来查找方程 (x - 1)^n - (x^n - 1) 的系数，如果所有这些系数都可以被主要候选者整除，则返回 True。

def isPrime(n):
    if n < 2:
        return False
    poly1 = np.polynomial.polynomial.polypow([1, -1], n)
    poly2 = np.zeros(n + 1, dtype=int)
    poly2[0] = 1
    poly2[-1] = -1
    coefficients = np.polysub(poly1, poly2)
    divisibility_test = lambda x : x % n != 0
    non_divisibles = filter(divisibility_test, coefficients)
    try:
        _ = next(non_divisibles)
        return False
    except StopIteration:
        return True

我知道我这里没有最高效的解决方案。我很困惑为什么这个实现只对低于 59 的输入产生正确答案。它无法识别任何大于 53 的素数。

编辑：演示结果的简单方法如下所示：

print(list(filter(isPrime, range(100))))

Answer 1

要使用 python 的任意精度整数，您可以在构造系数列表时指定 dtype=object 到适当的方法，即

poly1 = np.polynomial.polynomial.polypow(np.array([1, -1], dtype=object), n)
poly2 = np.zeros(n + 1, dtype=object)

Numpy AKS 素数函数

Numpy AKS primality function

python

primes

numpy

primality-test