CODEWITHSUNDEEP
javabiginteger
W.Howe
W.Howe

Reputation: 43

Negative exponents using the BigInteger class

I'm doing some maths using the Java BigInteger class but getting an error when I'm trying to use a negative number as an exponent. Am I right in thinking that you can rearrange:

b · φ(N)^−1 mod N

as:

      b
------------
φ(N)^1 mod N

If not how can I rearrange the expression as to not get a negative exponent error in my Java code?

Upvotes: 4

Views: 1025

Answers (2)

President James K. Polk
President James K. Polk

Reputation: 42019

Arithmetic mod N must be performed with modified rules. In particular inverses must be calculated much differently. The basic axiom of the inverse holds true:

x * x-1 = 1 mod N.

but you cannot compute x-1 mod N by computing 1/x as a floating point or decimal value. Instead, you must use an algorithm specifically for this purpose. Usually a variant of the extended euclidean algorithm is used.

Conveniently, Java's BigInteger class already includes this algorithm for you: modInverse(). So your calculation should look something like:

BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
BigInteger phiInverse = phi.modInverse(N);
BigInteger result = b.multiply(phiInverse).mod(N);

Upvotes: 3

Sweeper
Sweeper

Reputation: 274835

BigInteger can't have negative exponents, because that would make it a fraction (1 over something), which is not an "integer".

Try using BigDecimal instead.

As for your rearrangement of the expression, it should be rearranged like this:

      b
------------  mod N
   φ(N)^1

Upvotes: 4

Related Questions