(Миллер-Рабин) Как работать с числами с большими показателями?

У меня есть реализация Миллера-Рабина

def MillerRabin(n,a):
    e = 0
    q = n-1
    while q % 2 == 0:
          e += 1
          q = q/2
    if a**q % n == 1:
       return 1
    for i in range(e):
        if a ** (q * 2 ** i) % n == n-1:
           return 1
    return 0

(n, minA, maxA) = map(int, sys.argv[1:4])
print [MillerRabin(n, a) for a in range(minA,maxA)]

Есть три входа: число, минимальное основание, максимальное основание. Функция работает нормально, когда число низкое. Но когда число слишком велико, я получаю сообщение об ошибке (контрольный пример: число = 12530759607784496010584573923, минимальное основание = 16, максимальное основание = 32)

    exponent must be at most 9223372036854775807

python sage
person Haroldy    schedule 14.04.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Используйте встроенную функцию pow. Он может принимать необязательный параметр мода

>>> help(pow)
Help on built-in function pow in module __builtin__:

pow(...)
    pow(x, y[, z]) -> number

    With two arguments, equivalent to x**y.  With three arguments,
    equivalent to (x**y) % z, but may be more efficient (e.g. for longs).

def MillerRabin(n, a):
    e = 0
    q = n-1
    while q % 2 == 0:
          e += 1
          q = q // 2
    if pow(a, q, n) == 1:
       return 1
    for i in range(e):
        if pow(a , (q * 2 ** i) , n) == n - 1:
           return 1
    return 0
person John La Rooy    schedule 14.04.2015