BigInteger exponentiation with BigInteger number: ArithmeticException, would overflow supported range

user_15498100 0
Viewed 130

I'm building the DSA algorithm. But I had a problem when ranking BigInteger numbers with other BigInteger numbers. This is the formula I want to use:

v = ((g^u1 * y^u2) mod p) mod q

This is the code I made:

BigInteger v = g.pow(u1.intValue()).multiply(y.pow(u2.intValue())).mod(p).mod(q);

When running the script, the error is:

Exception in thread "main" java.lang.ArithmeticException: BigInteger would overflow supported range
        at java.math.BigInteger.reportOverflow(Unknown Source)
        at java.math.BigInteger.pow(Unknown Source)
        at DSAVerifying.main(DSAVerifying.java:38)
exponentiation java
1 Answers

To expand on my comment and because I could not find a duplicate: use modPow!

The problem here is that g^u1 (and y^u2) is REALLY large. But very often when dealing with powers in maths you have a mod statement following it and that simplifies stuff a lot: generally a ^ b mod c can be expressed as ((((a * a) mod c) * a) mod c) * a) mod c ..... (b times). And that is basically what modPow does, it applies the mod during the exponation. This will return the same number but will not overflow. They are mathematically identical, but one can be calculated by a computer with reasonable effort while the other cannot. It is up to you as the developer to be smart and simplify or rephrase the expression you want to solve in a way that a computer can properly handle.

BigInteger v = g.modPow(u1, p).multiply(y.modPow(u2, p)).mod(p).mod(q);

Basically to compute (6 ^ 10 mod 7) you do not ever want to first calculate 6 ^ 10 and then apply the mod 7 but instead do 6 * 6 mod 7 = 36 mod 7 = 1 => 1 * 6 mod 7 = 6 => 6 * 6 mod 7 = 36 mod 7 = 1 => ... and you can see that the only values you deal with are 1 and 6 instead of 60466176 (which is 6^10).

user_24428040
Related