Modular Exponentiation in Java

Question

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.

Immoderate

yes, p is prime, I think this solves it: (g^u * y^v) mod p = (g^u mod p) * (y^v mod p) mod p, though I have only tested it with small numbers so far – Immoderate

And is it large? The mod p part looks to me like if you wanted to use BigInteger instead of long. – Borras

yes, p is large (in my case, 23929 to be specific) – Immoderate

Answer 1

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.

Enfilade

yes, I think this is the way, so far I've done tests on small numbers with this, and it seems to be working – Immoderate

I'm guessing that it's probably not OK to assume that the factors will not overflow, but I can't be sure. – Cubital

The factors will not overflow as long as (p-1)*(p-1) fits inside an int. Otherwise, we will just have to use longs for x and y. The fact – Deglutinate

Answer 2

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.

Raffarty

It is indeed for cryptographic purposes, but it is for a school assignment where we are to implement the DSA ourselves. Thank you for your insightful answer! – Immoderate

Answer 3

Try

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

Insidious

I'm guessing the reason that he is asking is that the numbers are too big for the simple approach to work... – Cubital

If that is the case, why not use BigInteger? – Subconscious

Math.pow() takes and returns doubles. download.oracle.com/javase/1.4.2/docs/api/java/lang/… – Raffarty

Answer 4

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);
    }

Lorenzetti