CODEWITHSUNDEEP
javabiginteger
user1019710
user1019710

Reputation: 321

Java How to invert a BigInteger?

I need to invert a BigInteger.

Let's say i have BigInteger x; and i need to calculate x.modPow(new BigInteger("-1"), p).

I receive the following error: java.lang.ArithmeticException: BigInteger not invertible.

Upvotes: 6

Views: 7663

Answers (2)

Jason S
Jason S

Reputation: 189646

Use BigInteger.modInverse() -- it will do what you want.

If you read the docs for BigInteger.modInverse() (which performs the identical calculation, but more efficiently than your code; in fact presumably BigInteger.modPow() calls modInverse() for negative inputs before raising to a power), you'll see:

Throws: ArithmeticException - m <= 0, or this BigInteger has no multiplicative inverse mod m (that is, this BigInteger is not relatively prime to m).

If you're getting "BigInteger not invertible" this means that x and p are not relatively prime, so there is no mathematically defined inverse for the pair of numbers x and p given as input.

Possibilities:

  • p is prime, and x is 0 or a multiple of p
  • p is not prime, and x and p have a common factor
  • p is not a positive integer (0 or negative), which violates the requirements of modPow() and modInverse()

Upvotes: 6

corsiKa
corsiKa

Reputation: 82559

Just put return BigInteger.ZERO. Any time you invert a number greater than one, your result is between 0 and 1. When this number is represented as an integer, it ends up being 0...

Upvotes: -2

Related Questions