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 次方n。从p^n (mod x) == p^(k1) (mod x) . p^(k2) (mod x) . ... p^(kn) (mod x)wheresum k_i = n开始，您可以利用这个和两个的连续幂来逐步计算它O(log n)。

Answer 2

修改 2^32 的简单方法是使用& 0xFFFFFFFFL. 此外，碰巧有一种类型自然保持最低 32 位调用int；）如果您使用它，您甚至不需要执行，&直到您得到结果（所以答案是无符号的）因此，您只需要保留答案的最后 32 位。为了加快计算速度，^n您可以计算平方、平方和平方等，例如，如果 n 为 0b11111，那么您需要将 p^16 * p^8 * p^4 * p^2 * p 相乘。

简而言之，您可以使用 plain 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

Answer 3

除了其他答案之外，您还可以使用一些基本数论来将计算奇数的ⁿ mod 2 ³²所需的时间减少a到 O(1)。Euler Phi 函数与欧拉定理一起允许您丢弃除 n 的低 31 位以外的所有位 。

φ(2 ³² ) = 2 ³¹，并且^{φ(2 32 )} = 1 mod 2 ³²。

因此，如果 n = q*(2 ³¹ ) + r, 0 <= r < 2 ³¹，则ⁿ mod 2 ³² = a ^r mod 2 ³²

r 只是 n 的低 31 位，即n & 0x7fffffff。事实上，根据卡迈克尔定理，你可以做得更好（字面意思），你只需要考虑 n 的低 30 位，即n & 0x3fffffff。对于给定的 base ，您可以预先计算一次并将它们存储在大小为 4GB 的表中a。以下是一些 java 代码作为示例。

import java.math.BigInteger;

public class PowMod2_32 {

    private static final long MASK32 = 0xffffffffL;

    public static long pow32(final int a, final int exponent)
    {
        int prod = 1;

        for (int i = 29; i>=0; i--) {
            prod *= prod; // square
            if (((exponent >> i) & 1) == 1) {
                prod *= a;  // multiply
            }
        }
        return prod & MASK32;
    }

    public static long pow32(BigInteger a, BigInteger exponent) {
        return pow32(a.intValue(), exponent.intValue());
    }
}

Answer 4

我知道 java 中没有技巧，但数学中有一些技巧。

如果您将这些实现为算法，它应该会加快计算速度。

看 5 和 6。如果 2 的幂总是偶数，也看 4

Answer 5

使用类 Bigintiger。这是一个如何使用它的例子

public String higherPow() {
    BigIntiger i = new Bigintger("2");
    // doing a power(2^32)
    i = i.pow(32);
    // after 2^32 was made, do mod 100
    i = i.mod(new Bigintiger("100"));
    return i.toString();
}