使用 BigInteger 数的 BigInteger 求幂：ArithmeticException，会溢出支持的范围

Question

我正在构建 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)

Answer 1

要扩展我的评论，因为我找不到重复的评论：使用 modPow!

这里的问题是 g^u1（和 y^u2）真的很大。但通常在处理数学中的幂时，后面会有一个 mod 语句，这会大大简化事情：通常 a ^ b mod c 可以表示为 ((((a * a) mod c) * a) mod c) * a) mod c .....（b 次）。这基本上就是 modPow 所做的，它在扩展期间应用 mod。这将 return 相同的数字但不会溢出。它们在数学上是相同的，但是一个可以通过计算机通过合理的努力计算出来，而另一个则不能。作为开发人员，您需要聪明地以计算机可以正确处理的方式简化或改写您想要解决的表达式。

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）。

使用 BigInteger 数的 BigInteger 求幂：ArithmeticException，会溢出支持的范围

BigInteger exponentiation with BigInteger number: ArithmeticException, would overflow supported range

java

exponentiation

dsa