BigInteger用BigInteger取幂：ArithmeticException，会溢出支持的范围
我正在构建 DSA 算法。但是我在将 BigInteger 数字与其他 BigInteger 数字进行排名时遇到了问题。这是我想使用的公式：
v = ((g^u1 * y^u2) mod p) mod q
这是我制作的代码：
BigInteger v = g.pow(u1.intValue()).multiply(y.pow(u2.intValue())).mod(p).mod(q);
运行脚本时，错误是：
Exception in thread "main" java.lang.ArithmeticException: BigInteger would overflow supported range
at java.math.BigInteger.reportOverflow(Unknown Source)
at java.math.BigInteger.pow(Unknown Source)
at DSAVerifying.main(DSAVerifying.java:38)
回答
扩展我的评论，因为我找不到重复的：使用modPow！
这里的问题是g^u1（和y^u2）真的很大。但是很多时候在处理数学中的幂时，你会在它后面有一个 mod 语句，这简化了很多事情：通常a ^ b mod c可以表示为((((a * a) mod c) * a) mod c) * a) mod c .....(b 次)。这基本上就是什么modPow，它mod在论证期间应用。这将返回相同的数字但不会溢出。它们在数学上是相同的，但可以通过计算机通过合理的努力来计算，而另一个则不能。作为开发人员，您有责任以计算机可以正确处理的方式简化或重新表述您想要解决的表达式。
BigInteger v = g.modPow(u1, p).multiply(y.modPow(u2, p)).mod(p).mod(q);
基本上要计算，(6 ^ 10 mod 7)您永远不想先计算6 ^ 10然后应用，mod 7而是这样做6 * 6 mod 7 = 36 mod 7 = 1 => 1 * 6 mod 7 = 6 => 6 * 6 mod 7 = 36 mod 7 = 1 => ...，您可以看到您处理的唯一值是 1 和 6 而不是60466176（即6^10）。
- `u1.intValue()` -> `u1`. `u2.intValue()` -> `u2`. See [modPow](https://docs.oracle.com/en/java/javase/16/docs/api/java.base/java/math/BigInteger.html#modPow(java.math.BigInteger,java.math.BigInteger))
THE END
二维码