素数测试比蛮力法花费的时间更长，我该如何改进？

Question

我正在尝试在一台机器上计算质数，大小约为 2^30-2^100。
我的算法包含在下面供任何感兴趣的人使用。
我已将此 Python 代码优化为每个数字的 O(sqrt(n/2))（我相信）：它只接受奇数，并且我确保传递给它的数字在另一种方法中是奇数。

我使用了 费马素数测试 来尝试加快这个过程。但是，对于内置的 math.pow() 方法来说，数字太大了，所以我使用了平方取幂。
但是，对于较大的数字，这会花费很长时间——仅使用蛮力会更快。

我的实现有误吗？
时间来自于平方算法，它的递归栈也占了我的内存，有没有更快的算法我应该研究一下？

为了计算数字 35184372088967 是否为素数，使用我的强力算法花费了 .00100111 秒，但运行素数测试花费了 .40608 秒。

暴力素数检查：

def isPrime(n):
    for i in range(3,int(math.sqrt(n)),2):
        if(n%i==0):
            return False
    return True

费马算法的实现：

def couldBePrime(n):
        if(n>308):
            return power(2,n-1)%n==1
        else:
            return math.pow(2,n-1)%n==1

平方算法求幂（耗时部分）：

def power(base,exp):
    if exp == 0:
        return 1
    elif exp == 1:
        return base
    elif (exp & 1) != 0:
        return base * power(base * base, exp // 2)
    else:
        return power(base * base, exp // 2)

Answer 1

错误：math.pow计算浮点值。浮点计算是近似的，在这里会给你无意义的结果。您需要整数计算，例如您在 power 函数中所做的（效率低下）。 Python 的内置 ** 运算符和 pow 函数（不是 math.pow，这是一个不同的函数）都对整数进行运算。

在 Python 中，与许多编程语言一样，名为 math 的库专门用于浮点计算，而不是其他类型的数学计算，例如对整数进行的计算。

Inefficiency: 要计算b^e mod n，执行算术modulo n效率会高很多，而不是先计算b^e 然后将结果除以 n。计算 b^e 需要建立一个非常大的数字，这会很慢，因为随着计算 b 的幂越来越大，数字会很快变大。（计算 b^e 的最佳方法不容易确定，但所有方法都涉及计算 b 的中间幂，唯一实际不确定的是顺序。）当你想要结果 modulo n 时，做所有连续的乘法modulo n：计算b^2modn，然后平方并减少modulo n得到b^4modn，等等每次你执行一个乘法，在你做任何其他事情之前取除 n 的余数。

在Python中，标准库函数pow（记住，不是 math.pow）会为你做这件事。就这么简单

def couldBePrime(n):
    return pow(2, n-1, n) == 1

如果 Python 没有这个函数，那么你的 power 函数是一个合理的实现它的方法，如果你减少每个中间结果 modulo n.

def power(base, exp, mod):
    if exp == 0:
        return 1
    elif exp == 1:
        return base % mod
    elif (exp & 1) != 0:
        return (base * power((base * base) % mod, exp // 2, mod)) % mod
    else:
        return power((base * base) % mod, exp // 2)

当然，调用内置函数要快得多，这既是因为这是一种不错但不是非常好的执行操作的方法，也是因为 Python 为了便于编写比为了提高速度，最好将尽可能多的繁重的数字工作留给内置函数。

附加说明：要计算 2 的幂，有一种比乘法快得多的方法 — bit shifting。但这在这里没有帮助，因为您想计算 2^e mod n 而不是 2^e.

素数测试比蛮力法花费的时间更长，我该如何改进？

Primality test taking longer than brute force method, how can I improve?

python

optimization

primes

bignum

modular-arithmetic