python - 在 python 中优化/纠正我的米勒拉宾素数测试

Question

这是我的代码：

    import random
def one_d(n):
    b = n
    # initialize n
    s = 0
    # while loop, terminating when s becomes odd
    while n % 2 == 0:
        # increment s
        s = s+1
        # divide n by 2
        n = n/2
    tuple1 = tuple([s,n])
    return tuple1
    print "2^",s,"*",n,"=", b
def miller_rabin(n, a):
    list1 = []
    tuple1 = one_d(n-1)
    for r in xrange(tuple1[0]):
        list1.append((a**(2**(r)*tuple1[1])) % n)
        if list1[r] == n-1 or list1[r] == 1:
            return "True"
    else:
        return "False"
def isprime(n):
    for i in xrange(10):
        a = random.randrange(2, n-1)
        if miller_rabin(n, a) == "False":
            return "False"
    return "True

据我了解，这个测试应该能够处理非常大的数字，但我的脚本卡在 50034901 之类的数字上。我假设我在某处犯了错误/效率严重低下 - 因为我的脚本仍然适用于较小的数字.

Answer 1

好的，经过进一步调查，我意识到这是因为我使用“%”代码来执行模数计算，这比使用 python 的“pow”函数效率低得多。前者在计算模数之前计算完整指数，因此必须处理非常大的数字。后者分步进行，每次按模数 n 重新调整，因此效率更高