Java pow BigInteger 实现

Question

我正在研究密码学实现，部分设计包括以下内容：

( (y^a)^b / (y^c)^b ) mod p

我有以下片段：

BigInteger yab = y.pow(ab.intValue());
BigInteger ycb = y.pow(cb.intValue());

BigInteger ans = (yab.divide(ycb)).mod(p);

它适用于小整数。一旦我用生成的密钥替换它，指数就会变得如此之大，我将遇到 "BigInteger out of int range" 错误。我尝试了 modPow 函数，但结果不同。

我知道将其转换为 int 有其局限性。这是否意味着我的实施不可行？

Answer 1

您可以简化代码，这也会使其更快

x^y / x^z = x^(y - z)

所以

BigInteger yab = y.pow(ab.intValue());
BigInteger ycb = y.pow(cb.intValue());

BigInteger ans = (yab.divide(ycb)).mod(p);

可以简化为

BigInteger yabc = y.pow((int) (ab.longValue() - cb.longValue()));
BigInteger ans = yabc.mod(p);

或

BigInteger and = y.modPow(ab.minus(cb), p);

Answer 2

您似乎在 组中进行模运算，其中 n 是素数（在您的例子中是 n = p)。这意味着

x / y

不是除法，而是 x 与 y^-1 的乘法（ y).

的模逆

好在BigIntegerclass提供了这样的方法：

BigInteger ans = yab.multiply(ycb.modInverse(p)).mod(p);

其中 yab 和 ycb 可以有效计算而不会溢出（假设 ab 是 a 和 b 的乘积）：

BigInteger yab = y.modPow(ab, p);
BigInteger ycb = y.modPow(cb, p);