C# 快速模指数运算 快速求余运算

此方法解决这样一个问题，就是a^b mod m 的余数是多少。

如果直接计算a^b，方次很大的时候，会溢出，而且时间很长。

当然指数很小的时候直接用自带的Math函数就行，如果指数很大的时候，可以用以下的方法。

原理是利用模运算的分配率：

举例 56 mod 3=(7x8) mod3=(7 mod 3)x(8 mod 3)=1x2=2

public static ulong ModPow(ulong baseValue, ulong exponent, ulong modulus)  {  // 初始化结果为1，因为任何数的0次方都是1  ulong result = 1;  // 底数对模数取模，以防底数过大  baseValue %= modulus;  // 当指数不为0时，继续循环  while (exponent > 0)  {  // 如果当前指数是奇数，将底数乘到结果上，并取模  if ((exponent & 1) == 1)  result = (result * baseValue) % modulus;  // 底数平方并取模  baseValue = (baseValue * baseValue) % modulus;  // 指数右移一位（等同于除以2）  exponent >>= 1;  }  // 返回结果  return result;  }