在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和费马小定理（有关Rosetta代码对前者的实现，请参见here。

尽管概率选项比暴力破解快一个数量级，但是对于很大的n输入（例如，已知的质数10**9999 + 33603），它们仍然很慢。

我遇到了一个有趣的观察结果（当然我不是第一个遇到这样的观察结果的人），all素数适合方程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是质数，则上述保证返回true，但结果为真并不意味着p是质数。一个简单的例子是25（25 = 1（mod 6），但显然25 = 5 ^ 2）。

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

Answer 1

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

Answer 2

我在下面镜像的math.stackexchange（here）上发布了一个非常有用的解决方案

---

就此算法而言，您建议的“更快”算法等效于

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的素数，将使其相当无用。

---

Primality测试就其性质而言，在当前硬件上相当昂贵。您能做的最好的就是尝试针对输入中的某些给定假设进行优化。