Modular exponentiation function returns the wrong int value

Question

I got a modular exponentiation function in C which looks like this.

int modexp(int m, int e, int n)
{
    printf("%i\n", m);
    printf("%i\n", e);
    printf("%i\n", n);
    printf("\n");

    if(e == 0)
    {
        return 1;
    }
    if(e%2 == 1)
    {
        return modexp(m, e-1, n) * m%n;
    }
    else
    {
        int modTemp = modexp(m, (int)(e/2), n);
        modTemp = modTemp * modTemp;
        return modTemp % n;
    }
}

which I am calling in my main() function like this

int p = 3511;
printf("%i\n", modexp(2, p-1, p*p));

When printing the values for m, e and n I get the correct recursion values up to e = 0 in the end. This is when the function should return 1. It definitely returns at that position in the code, however instead of the expected integer 1, I get -6593454 and I have no idea why.

The full code can be found here: https://gist.github.com/anonymous/7024ac77b2432a381968

any input is highly appreciated...

Answer 1

Multipying an n-bit value with an m-bit value produces a (n+m)-bit result. That's why modexp(m, e-1, n) * m and modTemp * modTemp overflow. You need a widening multiplication to get the full 64-bit result from 32-bit values

return ((int64_t)modexp(m, e-1, n) * m) % n;
...
int64_t modTemp = modexp(m, (int)(e/2), n);
modTemp = modTemp * modTemp;
return modTemp % n;