时间戳

首页 > 解决方案 > BigInteger 指数与 BigInteger 数：ArithmeticException，会溢出支持的范围

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

标签： javaexponentiationdsa

解决方案

扩展我的评论并且因为我找不到重复：使用modPow！

这里的问题是g^u1(and 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）。

推荐阅读