java幂指数法不断返回错误值

ct2axkht 于 2021-07-12 发布在 Java

关注(0)|答案(1)|浏览(311)

我正在做一个小的加密程序，需要一个函数来计算功率模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;
}

但我注意到它在某些情况下返回了错误的答案。例子：
56295^779 mod 69997应返回53580，但返回20366
43576^7116 mod 50087应返回35712，但返回40613
它并不总是返回错误的答案，所以我不知道为什么会发生这种情况。有什么建议吗？

Java cryptography diffie-hellman exponentiation

来源：https://stackoverflow.com/questions/67223616/java-power-exponentiation-method-keeps-returning-wrong-value

1条答案

按热度按时间

3duebb1j1#

你是整数溢出的受害者。

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

这条线可能溢出。res*x不能保证适合有符号整数。
示例：

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

为了防止这种情况发生，你可以做一个 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
}

赞(0）回复(0）举报 2021-07-12

我来回答

java幂指数法不断返回错误值

1条答案

相关问题

热门标签

最新问答