费马素数测试太慢 - 大整数问题

Question

这是我的费马素数测试代码：

def fermat(n):
    counter = 0
    prime = False
    if n >= 40:
        upper_bound = 40
    else:
        upper_bound = n - 1

    for a in range(2, upper_bound + 1):
        print(a)
        if pow_mod(a, n - 1, n) == 1:
            counter += 1

    if counter == n - 2 and upper_bound == n - 1 or counter == 39 and upper_bound == 40:
        prime = True

    return prime

pow_mod 函数通过重复乘法计算 a^b mod n，每次应用 mod n，如下所示：

def pow_mod(a, b, n):
        result = 1
        for i in range(b):
            result = result * a % n
        return result

它适用于相对较小的素数。但是，如果我运行它用于大质数，例如 67280421310721，它不会在理想的时间内产生结果。是因为人数多吗？我该如何解决这个问题？

Answer 1

那是因为你的 pow_mod 太慢了。使用 fast algorithm 或仅使用 Python 的 built-in pow 函数。

顺便说一句，如果我正确理解了您相当复杂的代码，您只是在检查所有测试是否成功。哪个可以写的更清楚：

def fermat(n):
    upper_bound = 40 if n >= 40 else n - 1
    return all(pow(a, n - 1, n) == 1
               for a in range(2, upper_bound + 1))

费马素数测试太慢 - 大整数问题

Fermat primality test too slow - issues with big integers

python

math

primes