在 java 中计算 (a^b)%m

Question

在尝试实现 Miller-Rabin primality test 时，我遇到了 java 的奇怪行为。请看以下代码：
long x = (long) (Math.pow(a, b));
对于足够大的 a 和 b （不需要那么多），您将始终得到 x = 9223372036854775807 = Long.MAX_VALUE 而不是溢出值。
这个结果是完全没有用的，不会帮助计算 (a^b)%m，这正是我们需要的。
现在因为 (a^b)%m 很容易适合 64 位而 (a^b) 不适合，我想知道是否有一种方法可以在不使用 BigInteger?

的情况下计算这个数字

Answer 1

使用BigInteger，特别是方法modPow()。来自 javadocs：

public BigInteger modPow(BigInteger exponent, BigInteger m) - Returns a BigInteger whose value is (this^exponent mod m). (Unlike pow, this method permits negative exponents.)

https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#modPow(java.math.BigInteger,%20java.math.BigInteger)

例如：

BigInteger a = BigInteger.valueOf(2);
BigInteger b = BigInteger.valueOf(3);
BigInteger m = BigInteger.valueOf(7);

BigInteger result = a.modPow(b, m);  // i.e. 2 ^ 3 mod 7 -> 8 mod 7 -> 1
System.out.println(result);  // prints 1

Answer 2

您始终可以自己实施 pow(...) 并且 mod 尽可能多地实施。一般来说（伪代码）：

powMod(a, b, m) {
    result = 1
    for (i = 0; i < b; i++) {
        result = (result * a) % m
    }
    return result
}

如果 result * a 可能太大，那么您可能希望通过重复添加和在每个 + 之后添加 mod 来实现 *。此外，如果您还没有这样做，您可以（并且应该）始终使用 a' = a % m 和 b' = b % m。

在 java 中计算 (a^b)%m

computing (a^b)%m in java

java

math

long-integer