在 Python 中检查非常大数的素性 [英] Checking primality of very large numbers in Python

问题描述

检查给定大数是否为素数的最快方法是什么?我说的是大约 10^32 大小的数字.我已经尝试了 @MarcoBonelli 的精彩回答 中的算法:

What would be the fastest way to check if a given large number is prime? I'm talking about numbers the size of around 10^32. I've tried the algorithm from the great answer by @MarcoBonelli which is:

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)))

但它给出了错误 islice() 的停止参数必须是 None 或整数:0 <= x <= sys.maxsize 当用于如此大的数字时.那么有什么不同的、快速的方法来做到这一点?

but it gives the error of Stop argument for islice() must be None or an integer: 0 <= x <= sys.maxsize when used against such large numbers. What would be a different, fast way to do it then?

推荐答案

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

For a moderately large number I would use Miller-Rabin's Primality test. You can find Python code for it here: https://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test#Python

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

Note that the algorithm is probabilistic in nature, but applying it a number of time will guarantee correct answers with very high probability.

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

If you are absolutely set on using a trial division based method, I would recommend you multiply a large number of small primes and store the resulting composite number. Then you can take the Greatest Common Divisor (GCD) using a standard algorithm (such as 'fraction.gcd'). If the answer is not 1, then the number tested is definitely not prime. Usually you would then apply the Miller-Rabin test above to determine whether it is prime.

这篇关于在 Python 中检查非常大数的素性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！