使用Python处理大型素数 [英] Working with large primes in Python

问题描述

使用Python处理大型素数的有效方法是什么？您在此处或Google上搜索时，会发现许多不同的方法...筛子，素数测试算法...较大素数的工作方式是什么？

What is an efficient way for working with large prime numbers with Python? You search on here or on google, and you find many different methods for doing so... sieves, primality test algorithms... Which ways work for larger primes?

推荐答案

要确定数字是否为质数，请进行筛分和素性测试。

For determining if a number is a prime, there a sieves and primality tests.

# for large numbers, xrange will throw an error.
# OverflowError: Python int too large to convert to C long
# to get over this:

def mrange(start, stop, step):
    while start < stop:
        yield start
        start += step

# benchmarked on an old single-core system with 2GB RAM.

from math import sqrt

def is_prime(num):
    if num == 2:
        return True
    if (num < 2) or (num % 2 == 0):
        return False
    return all(num % i for i in mrange(3, int(sqrt(num)) + 1, 2))

# benchmark is_prime(100**10-1) using mrange
# 10000 calls, 53191 per second.
# 60006 function calls in 0.190 seconds.

这似乎是最快的。还有另一个使用 not 的版本，

This seems to be the fastest. There is another version using not any that you see,

def is_prime(num)
    # ...
    return not any(num % i == 0 for i in mrange(3, int(sqrt(num)) + 1, 2))

但是，在基准测试中，我在0.272秒内调用了 70006函数。在0.190秒内使用 all 60006函数调用。测试 100 * * 10-1 是质数。

However, in the benchmarks I got 70006 function calls in 0.272 seconds. over the use of all 60006 function calls in 0.190 seconds. while testing if 100**10-1 was prime.

如果您需要查找下一个最高质数，则此方法对您不起作用。您需要进行素数测试，我发现 Miller-Rabin 算法成为一个不错的选择。 Fermat 方法要慢一些，但对伪素数更准确。在系统上使用上述方法需要+5分钟。

If you're needing to find the next highest prime, this method will not work for you. You need to go with a primality test, I have found the Miller-Rabin algorithm to be a good choice. It is a little slower the Fermat method, but more accurate against pseudoprimes. Using the above mentioned method takes +5 minutes on this system.

Miller-Rabin 算法：

from random import randrange
def is_prime(n, k=10):
    if n == 2:
        return True
    if not n & 1:
        return False

    def check(a, s, d, n):
        x = pow(a, d, n)
        if x == 1:
            return True
        for i in xrange(s - 1):
            if x == n - 1:
                return True
            x = pow(x, 2, n)
        return x == n - 1

    s = 0
    d = n - 1

    while d % 2 == 0:
        d >>= 1
        s += 1

    for i in xrange(k):
        a = randrange(2, n - 1)
        if not check(a, s, d, n):
            return False
    return True

Fermat 算法：

def is_prime(num):
    if num == 2:
        return True
    if not num & 1:
        return False
    return pow(2, num-1, num) == 1

要获得下一个最高质数：

To get the next highest prime:

def next_prime(num):
    if (not num & 1) and (num != 2):
        num += 1
    if is_prime(num):
        num += 2
    while True:
        if is_prime(num):
            break
        num += 2
    return num

print next_prime(100**10-1) # returns `100000000000000000039`

# benchmark next_prime(100**10-1) using Miller-Rabin algorithm.
1000 calls, 337 per second.
258669 function calls in 2.971 seconds

使用 Fermat 测试中，我们得到的基准测试 45006在0.885秒内调用了函数。，但是伪素数的机会更高。

Using the Fermat test, we got a benchmark of 45006 function calls in 0.885 seconds., but you run a higher chance of pseudoprimes.

因此，如果只需要检查数字是否为质数，则 is_prime 的第一种方法就可以了。如果它与 mrange 方法一起使用，它是最快的。

So, if just needing to check if a number is prime or not, the first method for is_prime works just fine. It is the fastest, if you use the mrange method with it.

理想情况下，您希望存储由 next_prime 生成的素数，并从中读取。

Ideally, you would want to store the primes generated by next_prime and just read from that.

例如，使用 next_prime 和 Miller-Rabin 算法：

print next_prime(10^301)

# prints in 2.9s on the old single-core system, opposed to fermat's 2.8s
1000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000531

您将无法通过全部返回（及时将mrange（3，int（sqrt（num））+ 1，2）中的i个num％i换成i）。我什至不能在这个旧系统上做到这一点。

You wouldn't be able to do this with return all(num % i for i in mrange(3, int(sqrt(num)) + 1, 2)) in a timely fashion. I can't even do it on this old system.

并确保 next_prime（10 ^ 301）和 Miller-Rabin 产生正确的值，也使用 Fermat 和 Solovay-Strassen 算法。

And to be sure that next_prime(10^301) and Miller-Rabin yields a correct value, this was also tested using the Fermat and the Solovay-Strassen algorithms.

请参阅： fermat.py ， miller_rabin.py 和<在 gist.github.com

编辑：修复了 next_prime

这篇关于使用Python处理大型素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！