（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功能。它可以採取一個可選的MOD參數

>>> 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