BigIntegers to the power of BigInteger (Schnorr signature)

Question

I am trying to implement Schnorr signature algorithm in Java. I faced with problem to calculate power with big exponent (such as MD5 hash number).

Is there any way to get BigInteger in power of BigInteger?

I need to calculate (a^x*b^y) % z where y is extremely large number. Are there any method of calculating such expressions?

Thanks

Answer 1

I finally I found the solution. I can calculate my expression very fast using this technique:

(a * b) % p = ((a % p) * (b % p)) % p

So my example will look like this:

(a^x * b^y) % z = ( ((a^x) % z) * ((b^y) % z) ) % z;

or, using BigInteger in Java:

BigInteger result = a.modPow(x, z).multiply( b.modPow(y, z) ).mod(z);

Answer 2

For the Schnorr Signature Algorithm, you actually want a combined power and modulus operation. Just doing a power operation by itself makes no sense, because of the potentially enormous size of the numbers involved.

You need to use the modPow method of the BigInteger class.

Answer 3

No. The maximum value a BigInteger supports is 2^{Integer.MAX_VALUE}-1. This clarifying sentence was added to the BigInteger javadoc in Java 8, but the implementation has been the same for quite a while.

BigInteger must support values in the range -2^{Integer.MAX_VALUE} (exclusive) to +2^{Integer.MAX_VALUE} (exclusive) and may support values outside of that range.

As others have pointed out, you may want to use modPow instead of calculating intermediate values.

As a comparison, there are an estimated 10⁸⁰ (or 2²⁶⁵) atoms in the universe.