Java幂幂求幂方法不断返回错误的值

Question

我正在做一个小型密码程序，需要一个函数来计算的幂模

我写了这个方法：

static int power(int x, int y, int p){
int res = 1; // Initialize result

x = x % p; // Update x if it is more than or equal to p

while (y > 0) {
res = ((res*x) % p)+p % p;
y-=1;
}
return res;
}

但我注意到，在某些情况下，它会返回错误的答案。示例：

56295^779 mod 69997应返回53580，但返回20366而不是

43576^7116 mod 50087应返回35712，但返回40613而不是

它并不总是返回错误的答案，所以我不确定为什么会发生这种情况。有什么建议吗？

Answer 1

您是整数溢出的受害者。

res = ((res*x) % p)+p % p;

这一行可能会溢出。res*x不能保证适合有符号的32位整数(但确实适合有符号64位整数(。

示例：

2147483647 * 2 = -2
1147483647 * 22 = -525163542

为了防止这种情况发生，可以将res设为long而不是int，然后在从函数返回时强制转换回int。

static int power(int x, int y, int p){
long res = 1; // Initialize as long to prevent overflow!

x = x % p;

while (y > 0) {
res = ((res*x) % p)+p % p; // No more overflow here!
y-=1;
}
return (int) res; // Cast result back to int
}