负数的BigInteger幂运算

Question

我想知道怎么用标准的Java 7库来实现和这段Python（使用sage）代码一样的功能：

def elGamalDecrypt(c1, c2, p, x):
    return Mod(c2*c1^(-x),p)

所有的数字都是BigInteger类型。

我尝试了很多方法，但都没有成功。在Python中，这个过程真的很简单而且很快。

Answer 1

这段话的意思是，这个公式应该能达到同样的效果，因为 c2 * c1^-x = c2 / (c1 ^ x) 这个等式是成立的。

BigInteger elGamalDecrypt(BigInteger c1, BigInteger c2, BigInteger p, int x) {
    return c2.divide(c1.pow(x)).mod(p);
}

Answer 2

Java 7中的BigInteger类有一个叫做modPow的方法，这个方法用于处理模幂运算。简单来说，你可以像下面这样使用它（虽然我没有测试过）：

c2.multiply(c1.modPow(x.negate(), p)).mod(p)

这个modPow方法只有在c1和p互质的情况下，才会接受一个负的指数-x。互质的意思是这两个数没有共同的因子（除了1）。这里的p听起来像是个质数，如果c1和p不是互质的，那c1就会被p整除，这样做幂运算就没有意义了，所以我觉得这应该不会是个问题。