java - Java 中的模幂运算

Question

我需要一种方法来计算:

(g^u * y^v) mod p

在 Java 中。

我发现了这个计算 (g^u) mod p 的算法:

int modulo(int a,int b,int c) {
    long x=1
    long y=a;
    while(b > 0){
        if(b%2 == 1){
            x=(x*y)%c;
        }
        y = (y*y)%c; // squaring the base
        b /= 2;
    }
    return (int) x%c;
}

效果很好，但我似乎找不到办法做到这一点

(g^u * y^v) mod p

因为我的数学能力很差。

在上下文中，它用于“简化”DSA 的 java 实现 - 验证部分需要解决这个问题。

Answer 1

假设这两个因素不会溢出，我相信你可以这样简化一个表达式:

(x * y) mod p = ( (x mod p)*(y mod p) ) mod p。我相信您可以从那里弄明白。