(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)]

共有三个输入：数字、最小基数、最大基数。数字低时功能正常。但是当数字太大时，我得到一个错误（测试用例是 number = 12530759607784496010584573923，min-base = 16，max-base = 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

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

(Miller-Rabin)How do I deal with number with large exponents?

python

sage