模幂函数返回错误的int值

Question

我在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

高度赞赏任何输入...

我在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 = ...

Answer 1

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

Answer 2

1确实在e == 0时返回，但是此返回值是对先前递归级别进行的计算中的一项。如果您像这样修改代码：

Answer 3

我同意这是modTemp变量的溢出。但是，为清楚起见，我建议仅将modTemp的类型从Int更改为long，并使用b / e / m更改m / e / n，如下所示：

Answer 4

您的电话号码已满。它们最有可能是32或64位有符号整数，这意味着最大大小可以是2 ³¹