python - (Miller-Rabin)如何处理大指数的数字？

Question

我有 Miller-Rabin 实现

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