Modular Exponentiation in Java

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.

That fragment of code implements the well known "fast exponentiation" algorithm, also known as Exponentiation by squaring.

It also uses the fact that (a * b) mod p = ((a mod p) * (b mod p)) mod p. (Both addition and multiplications are preserved structures under taking a prime modulus -- it is a homomorphism). This way at every point in the algorithm it reduces to numbers smaller than p.

While you could try to calculate these in an interleaved fashion in a loop, there's no real benefit to doing so. Just calculate them separately, multiply them together, and take the mod one last time.

Be warned that you will get overflow if p^2 is greater than the largest representable int, and that this will cause you to have the wrong answer. For Java, switching to big integer might be prudent, or at least doing a runtime check on the size of p and throwing an exception.

Finally, if this is for cryptographic purposes, you should probably be using a library to do this, rather than implementing it yourself. It's very easy to do something slightly wrong that appears to work, but provides minimal to no security.

Try

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

Here's some sample code that inputs the variables in the original question and follows on from Christian Mann's answer. BigInteger gets around the overflow issues. The return statement is a BigInteger.

    public static BigInteger ModularExponent(BigInteger G, BigInteger U, BigInteger Y, BigInteger V, BigInteger P) {
      
      return ((G.modPow(U,P)).multiply(Y.modPow(V,P))).mod(P);
    }