c# - 手动修改号码的快速方法

Question

我需要能够为非常大的 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;
    }

但这需要很长时间。有没有简单快速的方法来执行此操作，而实际上不必使用 a 的 b 次方并且不使用耗时的循环？如果一切都失败了，我可以创建一个 bool 数组来表示一个巨大的数据类型，并找出如何使用位运算符来实现这一点，但必须有更好的方法。

Answer 1

我想您正在寻找:http://en.wikipedia.org/wiki/Montgomery_reduction 或基于模幂的更简单方法(来自维基百科)

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