java - 返回大幂 (mod 2^32)

Question

我需要计算一个非常大的幂模 (2^32)，即我想要的结果是:

y = (p^n) mod (2^32)

p is a prime number
n is a large integer

在 Java 中是否有高效执行此操作的技巧？

还是我坚持在一个循环中进行 n 次迭代？

Answer 1

修改 2^32 的简单方法是使用 & 0xFFFFFFFFFL。此外，碰巧有一种类型自然保留最低的 32 位，称为 int ;) 如果你使用它，你甚至不需要执行 & 直到你得到结果(所以答案是无符号的)因此你只需要保留答案的最后 32 位。要加快 ^n 您可以计算平方，它是平方和它是平方等，例如，如果 n 是 0b11111 那么您需要乘以 p^16 * p^8 * p^4 * p^ 2 * 页。

简而言之，您可以使用普通的 int，因为您只需要 32 位的精度和值，成本为 O(ln n)，其中 n 是幂.

int prime = 2106945901;
for (int i = 0; i < 10; i++) {
    long start = System.nanoTime();
    long answer1 = BigInteger.valueOf(prime)
                             .modPow(
                                 BigInteger.valueOf(prime), 
                                 BigInteger.valueOf(2).pow(32)).longValue();

    long mid = System.nanoTime();
    int answer2 = 1;
    int p = prime;
    for (int n = prime; n > 0; n >>>= 1) {
        if ((n & 1) != 0)
            answer2 *= p;
        p *= p;
    }
    long end = System.nanoTime();
    System.out.printf("True answer %,d took %.3f ms, quick answer %,d took %.3f ms%n",
            answer1, (mid - start) / 1e6, answer2 & 0xFFFFFFFFL, (end - mid) / 1e6);
}

最后打印

True answer 4,169,684,317 took 0.233 ms, quick answer 4,169,684,317 took 0.002 ms