Java 幂幂法一直返回错误值
Java power exponentiation method keeps returning wrong value
我正在做一个小的密码学程序,需要一个函数来计算功率mod n
我写了这个方法:
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;
}
但我注意到它 return 在某些情况下是错误的答案。示例:
56295^779 mod 69997 应该 return 53580 但 return 应该是 20366
43576^7116 mod 50087 应该 return 35712 但 return 应该是 40613
它并不总是 return 一个错误的答案,所以我不确定为什么会这样。有什么建议吗?
你是整数溢出的受害者。
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
}
我正在做一个小的密码学程序,需要一个函数来计算功率mod n
我写了这个方法:
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;
}
但我注意到它 return 在某些情况下是错误的答案。示例:
56295^779 mod 69997 应该 return 53580 但 return 应该是 20366
43576^7116 mod 50087 应该 return 35712 但 return 应该是 40613
它并不总是 return 一个错误的答案,所以我不确定为什么会这样。有什么建议吗?
你是整数溢出的受害者。
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
}