大数模幂运算

Question

我正在尝试实现mod平方幂算法。

我有一些 class:

template< typename T>
class SomeMathFun {
    .....
}

它有方法：

static T ModularExp(T base, T exp, T modulo) {
    T result(1);
    base %= modulo;
    while (exp > 0) {
        if (exp & 1)
            result = (result * base) % modulo;
        exp >>= 1;
        base = (base * base) % modulo;
    }
    return result;
}

它适用于像 5^117 这样的小数字 mod 19：结果是 1。但是当我尝试处理大数字时，它就不太适用了。

例如：

unsigned int a(SomeMathFun<unsigned int>::ModularExp(120, 17, 80223667));
std::cout << a;

结果是：34313651。但这是不正确的。应该是70781811。

我做错了什么？实施错误还是我应该使用其他算法？

P.S.: 我对使用某些库中的函数不感兴趣，我对算法感兴趣，或者至少对一些实现正确工作算法的代码感兴趣，这样我就可以理解它是如何工作的。

Answer 1

问题出在整数乘法溢出。

大数模幂运算

Modular Exponentiation with big numbers

c++

algorithm

exponentiation

c++11

modular-arithmetic