Оптимизация / исправление моего теста первичности миллера Рабина в 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' в python. Первый вычисляет полный показатель до вычисления модуля и, следовательно, имеет дело с очень большими числами. Последний идет пошагово, каждый раз перенастраивается по модулю n и, таким образом, более эффективен