Modular Exponentiation in Java

java math modulus dsa exponentiation
Carl Hagen picture Carl Hagen · Nov 1, 2010 · Viewed 15.1k times · Source

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.

Answer

Christian Mann picture Christian Mann · Nov 1, 2010

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.

Related questions

How do I divide so I get a decimal value?

I want to know how to get remainder and quotient in single value in Java. Example: 3/2 I should get value as 1.5. If I use the / operator I get only the quotient. If I user the % operator I get only the …

Read More
Math.random() explanation

This is a pretty simple Java (though probably applicable to all programming) question: Math.random() returns a number between zero and one. If I want to return an integer between zero and hundred, I would do: (int) Math.floor(Math.…

Read More
How to evaluate a math expression given in string form?

I'm trying to write a Java routine to evaluate math expressions from String values like: "5+3" "10-40" "(1+10)*3" I want to avoid a lot of if-then-else statements. How can I do this?

Read More