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

看起来你正在组 中进行模运算其中 n 是质数(在您的情况下是 n = p)。这意味着

x / y

不是除法，而是 x 与 y^-1 的乘法(y 的模逆) )。

好消息是 BigInteger类提供了这样一个方法:

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);