Оптимизация Миллера-Рабина тест на простоту в Python


Я пишу Миллера-Рабина тест на простоту в Python. Пока я бегло посмотрел на то, как другие подошли к проблеме, я решил попробовать решить проблему самостоятельно. Помимо выбора языка, как я могу идти об оптимизации этого кода? Любые предложения приветствуются и не стесняйтесь быть честными.

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)


363
4
задан 5 марта 2018 в 12:03 Источник Поделиться
Комментарии
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 и вернуться прежде, чем идти через петлю несколько раз.

1
ответ дан 6 марта 2018 в 03:03 Источник Поделиться