当 A、B、M 是大数时，如何计算 (A^B)%M？

Question

例如A = 864927518,B = 1462579282,M = 193773611,如何计算(A^B)%M?

有没有简单的方法？

Answer 1

3>> pow(864927518, 1462579282, 193773611)
2767533

Answer 2

是：使用 modular exponentiation. Python's built in pow 函数允许您使用其可选的第三个参数执行此操作：

>>> pow(A, B, M)
2767533

Answer 3

我将愉快地假设您在这里使用 ^ 作为求幂运算符（而不是 XOR）。您可以使用内置的 pow 或者您可以编写自己的代码：

import math

def expmod(i, j, m):
  """Compute (i ** j) % m"""

  acc = 1
  mask = 2 ** int(math.ceil(math.log(j, 2)))
  while mask > 0:
    acc = acc * acc
    if mask & j:
      acc = acc * i
      j = j ^ mask
    mask = mask // 2
    acc = acc % m

  return acc