(Miller-Rabin) Как мне обрабатывать число с большими показателями?

Question

У меня Миллера-Рабина implemntation

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 

Answer 1

Используйте встроенный 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