Python中检查大整数是否为质数

Question

什么是检查给定大数是否为质数的最快方法？我说的是约为10 ^ 32大小的数字。我尝试了MarcoBonelli大神在Stackoverflow上的算法，它是：

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错误。那么有没有其他不同且更快的方法呢？

- Straightfw

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

- user448810

---

我建议使用"d>>1"而不是"d/2"，以便能够处理更大的数字。 - McSebi

Answer 2

对于一个相当大的数，我建议使用Miller-Rabin素性测试。你可以在这里查找它的Python代码：https://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test#Python

需要注意的是，该算法具有概率性质，但多次应用可以保证高准确率。

如果你非常想使用基于试除法的方法，我建议你将许多小质数相乘并存储结果组合数。然后，你可以使用标准算法（如'fraction.gcd'）来计算最大公约数（GCD）。如果答案不为1，则被测试的数绝对不是素数。通常，接下来你会应用上述的Miller-Rabin测试来确定它是否为素数。

- gdanezis