Search code examples
javacryptographybigintegerpowexponent

Java pow BigInteger implementation

I am working on a cryptography implementation and part of the design includes the following:

( (y^a)^b / (y^c)^b ) mod p

I have the following snippet:

BigInteger yab = y.pow(ab.intValue());
BigInteger ycb = y.pow(cb.intValue());

BigInteger ans = (yab.divide(ycb)).mod(p);

It works fine for small integer. Once I replaced it with generated keys, the exponent grew so huge and I will hit the "BigInteger out of int range" error. I have tried the modPow function but the result is different.

I understand that casting it to int has its limitation. Does that means my implementation is infeasible?

Solution

  • You can simplify the code and this will also make it faster

    x^y / x^z = x^(y - z)

    so

    BigInteger yab = y.pow(ab.intValue());
BigInteger ycb = y.pow(cb.intValue());

BigInteger ans = (yab.divide(ycb)).mod(p);

    can be simplified to 

    BigInteger yabc = y.pow((int) (ab.longValue() - cb.longValue()));
BigInteger ans = yabc.mod(p);

    or

    BigInteger and = y.modPow(ab.minus(cb), p);