在Python中检查非常大的数的素性

这是我对米勒-拉宾首要性测试的实施;默认为5次随机试验,但您可以根据需要进行调整。循环打开 p 是小素数的快速返回。

def isPrime(n, k=5): # miller-rabin
    from random import randint
    if n < 2: return False
    for p in [2,3,5,7,11,13,17,19,23,29]:
        if n % p == 0: return n == p
    s, d = 0, n-1
    while d % 2 == 0:
        s, d = s+1, d/2
    for i in range(k):
        x = pow(randint(2, n-1), d, n)
        if x == 1 or x == n-1: continue
        for r in range(1, s):
            x = (x * x) % n
            if x == 1: return False
            if x == n-1: break
        else: return False
    return True

对于一个适度大的数字,我会使用米勒-拉宾的Primality测试。您可以在这里找到Python代码: https://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test#Python

请注意,该算法本质上是概率性的,但多次应用它将确保正确答案的概率非常高。

如果你绝对要使用一种基于试算除法的方法,我建议你用大量的小素数相乘并存储合成的数字。然后,您可以使用标准算法(如“fraction.GCD”)计算最大公因子(GCD)。如果答案不是1,那么测试的数字肯定不是素数。通常你会应用上面的米勒-拉宾测试来确定它是否是质数。