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;  
    }