Modular expansion in Java

Question

I need a way to calculate:

(g^u * y^v) mod p

in java.

I found this algorithm to compute (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;
}

and it works fine, but I cannot find a way to do this for

(g^u * y^v) mod p

since my math skills are dull.

To put it in context, this is for the Java implementation of the “abbreviated” DSA — the validation part requires that it be allowed.

Answer 1

Assuming that the two factors will not overflow, I believe that you can simplify this expression as follows:

(x * y) mod p = ( (x mod p)*(y mod p) ) mod p. I'm sure you can figure it out from there.

Answer 2

" ", "" .

, (a * b) mod p = ((mod p) * (b mod p)) mod p. ( - - ). , p.

, . , .

, , p ^ 2 , int, . Java , , p .

, , , , . - , , .

Answer 3

(Math.pow(q, u) * Math.pow(y, v))% p