Python 中大 `n` 的快速素性测试

Question

我正在做一个项目，要求我找出极大的数是否是素数。当然，我已经阅读了如何查找素数并想出了一个非常简单的暴力破解方法：

def is_prime_brute_force(p):
    if p == 2 or p == 3:
        return true
    if p == 1 or p % 2 == 0 or any(p % i == 0 for i in range(3, floor_sqrt(p), 2)):
        return false
    return true

我还研究了 Miller-Rabin Primality Test and Fermat's little theorem (see here 等概率方法，用于前者的 Rosetta 代码实现。

虽然概率选项比蛮力快一个数量级，但对于非常大的 n 输入（例如，已知素数 10**9999 + 33603），它们仍然非常慢。

我发现了一个有趣的观察结果（当然我不是第一个发现这种观察结果的人），即所有个素数都符合方程 p = 6 * k + 1 或 p = 6 * k -1。在Python中，这样的函数看起来像这样

def is_prime_eq(p):
    if p == 2 or p == 3:
        return True
    if p == 0 or p == 1:
        return False

    # The same as `return (p % 6 == 1) or (p % 6 == 5)`
    prime_test = lambda p, a, m : (p % a == m) or (p % a == (a-m))
    return prime_test(p, 6, 1)

如果 p 是质数，则以上保证 return 为真，但结果为真并不意味着 p 是质数。一个简单的例子是 25 (25 = 1 (mod 6)，但显然 25 = 5^2).

我想知道是否有一些更通用的方法来应用这个有趣的属性素数，也许使用不同的 a 值来提高我的 is_prime 函数的速度。

Answer 1

只需使用概率测试。概率测试是素数测试的最新技术，比任何确定性测试都快得多，发明任何更快的东西都需要世界 class 数论专业知识。

gmpy2 可能是您在 Python 中的最佳选择。它具有 built-in support 用于多个概率素性测试和其他数论函数，以及它自己的任意精度 int 类型，该类型针对大值的更快操作进行了优化。

Answer 2

math.stackexchange (here) 上发布了一个非常有用的解决方案，我在下面进行了镜像

关于这个算法，你提出的"faster"算法等同于

def is_prime_brute_force(p):
    if p == 2 or p == 3:
        return true
    if p == 1 or p % 2 == 0 or p % 3 == 0:
        return false
    return true

希望您明白为什么这不是很有帮助。任何作为素数 >= 5 的乘积的组合都将评估为素数。通常我们对素数都足够大的数字使用概率素数测试（例如 Miller-Rabin），因此忽略所有大于 3 的素数会使它变得毫无用处。

素性测试本质上在当前硬件上成本相当高。您能做的最好的事情就是尝试针对输入的某些给定假设进行优化。

Python 中大 `n` 的快速素性测试

Fast primality testing for large `n` in Python

python

math

primes