I need a way to calculate:
(g^u * y^v) mod p
in Java.
I've found this algorithm for calculating (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 great, but I can't seem to find a way to do this for
(g^u * y^v) mod p
as my math skills are lackluster.
To put it in context, it's for a java implementation of a "reduced" DSA - the verifying part requires this to be solved.
Assuming that the two factors will not overflow, I believe you can simplify an expression like that in this way:
(x * y) mod p = ( (x mod p)*(y mod p) ) mod p
. I'm sure you can figure it out from there.