Modular Exponentiation in Java

java math modulus dsa exponentiation

16,129

Solution 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.

Solution 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.

Solution 3

Try

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

16,129

Carl Hagen

I am student of program who want to learn!

Updated on May 07, 2022

Comments

Carl Hagen almost 2 years
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.
Michael McGowan over 13 years

I'm guessing the reason that he is asking is that the numbers are too big for the simple approach to work...
Nicholas over 13 years

If that is the case, why not use BigInteger?
Michael McGowan over 13 years

I'm guessing that it's probably not OK to assume that the factors will not overflow, but I can't be sure.
MAK over 13 years

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
Carl Hagen over 13 years

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!
wnoise over 13 years

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