为什么我的费马素性检验算法这么慢？

Question

我正在学习数论。现在，我想写一个程序来执行费马素性测试。

首先，我写一个模平方算法：

#modular_square.py
def modular_square(a, n, m):
    res = 1
    exp = n
    b = a 

    while exp !=0 :

        if exp % 2 == 1:
            res *= b
            res %= m

        b *= b
        exp >>= 1

    return res


def main():
    a = [   12996,      312,        501,        468,        163]
    n = [   227,        13,         13,         237,        237]
    m = [   37909,      667,        667,        667,        667]
    res = [ 7775,       468,        163,        312,        501]
    #test modular_square()
    print("===test modular_square()===")
    for i, r in enumerate(res):
        if modular_square(a[i], n[i], m[i]) != r:
            print("modular_square() failed...")
        else:
            print("modular_square({},{},{})={}".format(a[i], n[i], m[i], r))  


if __name__ == "__main__":
    main()

然后，我在上述算法的基础上编写了费马素性检验算法。

#prime_test_fermat.py

import modular_square
import random

def Fermat_base(b, n):
    res = modular_square.modular_square(b, n-1, n)

    if res == 1:
        return True
    else:
        return False


def Fermat_test(n, times):

    for i in range(times):
        b = random.randint(2, n-1)
        if Fermat_base(b, n) == False:
            return False

    return True

def main():
    b = [8,         2]
    n = [63,        63]
    res = [True,    False]
    #test Fermat_base()
    print("===test Fermat_base()===")
    for i,r in enumerate(res):
        if Fermat_base(b[i], n[i]) != res[i]:
            print("Fermat_base() failed...")
        else:
            print("Fermat_base({},{})={}".format(b[i], n[i], res[i]))

    n = [923861,
        1056420454404911
         ]

    times = [2, 2]

    res = [True,True ]
    #test Fermat_test()
    print("==test Fermat_test()===")
    for i,r in enumerate(res):
        if Fermat_test(n[i], times[i]) != res[i]:
            print("Fermat_test() failed...")
        else:
            print("Fermat_test({},{})={}".format(n[i], times[i], res[i]))

if __name__ == '__main__':
    main()

当我运行 prime_test_fermat.py程序时，它没有停止。这是费马素数或者我的代码存在bug导致的。

Answer 1

问题出在您的模幂算法上：模数应用于 res 但未应用于 b。由于 b 在每次迭代中都被平方，因此它将变得非常大（如几千位）。这会减慢您的算法。

要解决这个问题，您还必须将模数应用于 b。将 b *= b 替换为：

b *= b
b %= m

作为额外的优化，您还可以在初始化 b 时应用模数，方法是将 b = a 替换为：

b = a
b %= m

你可以把这个pseudo-code当作reference。

为什么我的费马素性检验算法这么慢？

Why is my algorithm about Fermat primality test so slow?

python

exponentiation

number-theory

primality-test