Java 幂幂法一直返回错误值

Question

我正在做一个小的密码学程序，需要一个函数来计算功率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 一个错误的答案，所以我不确定为什么会这样。有什么建议吗？

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
}

Java 幂幂法一直返回错误值

Java power exponentiation method keeps returning wrong value

java

cryptography

diffie-hellman

exponentiation