Python中的模幂算法

Question

我创建了一个计算大模指数的函数。我知道这个函数是内置在python语言中的。我的函数对于大于17位数的数字是不正确的，我不知道为什么。非常感谢任何帮助。在

from random import randint

def modpow(x,n,m):
  if n == 0:
    return 1
  elif n == 1:
    return x
  elif n%2 == 0:
    return modpow(x*(x%m),n/2,m)%m
  elif n%2 == 1:
    return (x *  modpow(x*(x%m),(n-1)/2,m)%m )%m

for i in range(5,32):
  x = ''
  n = ''
  m = ''
  for j in range(i):
    x += str(randint(0,9))
    n += str(randint(0,9))
    m += str(randint(0,9))
  x = int(x)
  n = int(n)
  m = int(m)
  if pow(x,n,m) != modpow(x,n,m):
    print(i,x,n,m)

样本输出：

^{pr2}$

我已经运行了好几次，它总是在I=17时失败，我不太清楚原因。在

Answer 1

我的猜测是Python的pow()在底层工作于double。失败的第一个值的log base2（38508450670424585）大约是55，但是double只有53位的精度，因此大于2^53的整数不一定能精确表示。我的猜测是，如果你检查最后一个成功的数字的以2为基数的日志（即x=16），它将小于53。在