c - 模幂运算返回错误的int值

我在C中得到了一个模幂函数，它看起来像这样。

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

我在我的main()函数中这样调用

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

当打印m，e和n的值时，最后我得到正确的递归值，直到e = 0。这是函数应该返回1的时候。它肯定会在代码中的那个位置返回，但是不是预期的整数1，而是-6593454，我也不知道为什么。

完整的代码可以在这里找到：
https://gist.github.com/anonymous/7024ac77b2432a381968

任何输入都受到高度赞赏...

最佳答案

将n位值与m位值相乘会产生（n + m）位结果。这就是modexp(m, e-1, n) * m和modTemp * modTemp溢出的原因。您需要加倍乘法以从32位值获得完整的64位结果

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;