c# – 手动修改数字的快捷方式

我需要能够为a和b的非常大的值计算(a ^ b)％c(当你试图计算a ^ b时,它们分别是推动限制并且导致溢出错误).对于足够小的数字,使用标识(a ^ b)％c =(a％c)^ b％c可以工作,但如果c太大,这实际上没有帮助.我写了一个循环来手动执行mod操作,一次一个：

private static long no_Overflow_Mod(ulong num_base, ulong num_exponent, ulong mod) 
    {
        long answer = 1;
        for (int x = 0; x < num_exponent; x++)
        {
            answer = (answer * num_base) % mod;
        }
        return answer;
    }

但这需要很长时间.是否有任何简单快速的方法来执行此操作,而无需实际使用b AND的功能而不使用耗时的循环？如果所有其他方法都失败了,我可以创建一个bool数组来表示一个巨大的数据类型,并找出如何使用按位运算符来实现这一点,但必须有一个更好的方法.

我猜你在寻找： http://en.wikipedia.org/wiki/Montgomery_reduction

或者基于Modular Exponentiation的简单方法(来自维基百科)

Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) {

    Bignum result = 1;

    while (exponent > 0) {
        if ((exponent & 1) == 1) {
            // multiply in this bit's contribution while using modulus to keep result small
            result = (result * base) % modulus;
        }
        // move to the next bit of the exponent, square (and mod) the base accordingly
        exponent >>= 1;
        base = (base * base) % modulus;
    }

    return result;
}