Java 如何反转 BigInteger？

Question

我需要反转一个 BigInteger。

假设我有 BigInteger x;，我需要计算 x.modPow(new BigInteger("-1"), p)。

我收到以下错误:java.lang.ArithmeticException: BigInteger not invertible。

Answer 1

使用 BigInteger.modInverse()——它会做你想做的事。

如果您阅读了 BigInteger.modInverse() 的文档(它执行相同的计算，但比您的代码更有效；事实上大概是 BigInteger.modPow()在提升到幂之前调用 modInverse() 负输入)，你会看到:

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

如果您得到“BigInteger not invertible”，这意味着 x 和 p 不是互质的，因此作为输入给出的一对数字 x 和 p 没有数学上定义的逆。

可能性:

• p是素数，x是0或p的倍数
• p不是质数，x和p有公因数
• p 不是正整数(0 或负数)，违反了modPow() 和modInverse()
的要求