Modular Exponentiation with big numbers

Question

I'm Trying to implement modular exponentiation algorithm.

I have some class:

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

and it has method:

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

It works fine for small numbers like 5^117 mod 19: result is 1. But when I try to work with big numbers, it doesn't work well.

For example:

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

Result is: 34313651. But it's not correct. It should be 70781811.

What am I doing wrong? Wrong implementation or should I use some other algorithm?

P.S.: I'm not interested in using functions from some libraries, I'm interested in algorithm or at least some code which implements correct working algorithm so I can understand how it works.

Answer 1

The problem was in integer overflowing in multiplication.