1

我正在学习数论。现在，我想编写一个执行费马素性检验的程序。

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

#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程序时，它并没有停止。这是由 Fermat 素数或我的代码存在错误引起的。

4

1 回答 1

1

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

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

b *= b
b %= m

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

b = a
b %= m

您可以将此伪代码作为参考。

于 2020-09-11T12:22:34.673 回答