用Python优化Miller-Rabin素数检验

Question

我在用Python写一个Miller-Rabin原始性测试。当我简要地观察了其他人是如何处理这个问题的时候，我决定自己尝试解决这个问题。除了我选择的语言之外，我如何优化这段代码呢？任何建议都是受欢迎的，不要犹豫，要残忍地诚实。

def miller_rabin_primality_test(n):

    def mr_check_one(n):
        m = n - 1       
        n = n - 1       
        k =  1          

        while n % 2**k == 0:
            m = n / 2**k      
            k = k + 1         

        return(m)        

    def mr_check_two(n, m, a = [2, 3]):

        for i in range(0, len(a)):
            a = a[i]
            b = pow(a, m, n)
            i = 0

            if(b == n - 1 or b == 1):
                return True

            while(b != n - 1 and i < 7):
                b = pow(b, 2, n)
                i = i + 1

            if(b != n - 1): 
                return False
            else: 
                return True


    m =  mr_check_one(n) 
    r = mr_check_two(n, m)

    return(r)

Answer 1

一个明显的变化是，mr_check_one(n)所做的循环比必要的要昂贵得多。这里有一个更简单、更快的版本。

def mr_check_one(n):
    m = n - 1

    n = n - 1
    k =  1          
    while n % 2 == 0:  
        k += 1
        n /= 2

    return(m / 2**k) 

另外，你的第二个功能似乎真的坏了。据称，您在a上循环，但在您第一次通过您重新定义a，重置i和返回之前，循环不止一次。