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

Question

检查给定大数是否为素数的最快方法是什么？我说的是大约10 ^ 32的数字.我从@MarcoBonelli的优秀答案中尝试了这个算法,它是:

from math import sqrt; from itertools import count, islice

def isPrime(n):
    return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))

但它给出了Stop argument for islice() must be None or an integer: 0 <= x <= sys.maxsize用于对抗如此大数字时的错误.那会是一个不同的,快速的方法呢？

Answer 1

这是我对Miller-Rabin素性测试的实现; 它默认为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

Answer 2

对于中等大的数字，我会使用 Miller-Rabin 的 Primality 测试。你可以在这里找到它的 Python 代码：https : //rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test#Python

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

如果您绝对使用基于试除法的方法，我建议您将大量小素数相乘并存储结果合数。然后，您可以使用标准算法（例如“fraction.gcd”）计算最大公约数 (GCD)。如果答案不是 1，那么测试的数字肯定不是质数。通常你会应用上面的 Miller-Rabin 检验来确定它是否是素数。