Return a large power (mod 2^32)

Question

I need to work out a very large power modulo (2^32), i.e. I want the result of:

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

p is a prime number
n is a large integer

Is there a trick to doing this efficiently in Java?

Or am I stuck with doing it in a loop with n iterations?

Answer 1

The simple way to mod 2^32 is to use & 0xFFFFFFFFL. Also, there happens to be a type which naturally keeps the lowest 32-bit called int ;) If you use that you don't even need to perform the & until you have the result (so the answer is unsigned) For this reason you only need to keep the last 32 bit of the answer. To speed up the ^n you can calculate the square, it's square and it's square etc, e.g if n is 0b11111 then you need to multiply p^16 * p^8 * p^4 * p^2 * p.

In short, you can use plain int as you only need 32-bit of accuracy and values with a cost of O(ln n) where n is the power.

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);
}

prints finally

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

Answer 2

You can utilize exponentiation by squaring. Firstly, break it down into powers of two for your given n. Since p^n (mod x) == p^(k1) (mod x) . p^(k2) (mod x) . ... p^(kn) (mod x) where sum k_i = n, you can utilize this and successive powers of two to calculate this in O(log n) steps.

Answer 3

In addition to the other answers you can use some elementary number theory to reduce the time needed to compute aⁿ mod 2³² for a an odd integer to O(1). The Euler Phi function together with Euler's Theorem allows you to discard all but the low-order 31 bits of n.

φ(2³²) = 2³¹, and a^φ(232) = 1 mod 2³².

Thus if n = q*(2³¹) + r, 0 <= r < 2³¹, then aⁿ mod 2³² = a^r mod 2³²

r is simply the low-order 31 bits of n, i.e. n & 0x7fffffff. In fact, by Carmichael's Theorem you can do a bit better (literally), and you only need to consider the low-order 30 bits of n, i.e. n & 0x3fffffff. You can precompute these once and store them in a table of size 4GB for a given base a. Here is some java code as an example.

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

There are no tricks in java that I know of but rather there are some tricks in maths.

If you implement these as an algorithm it should speed up computation.

Look at 5 and 6. Look at 4 also if power of two is always even

Answer 5

Use the Class Bigintiger. here´s an example how to work / pow with it

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();
}