A use for overflow

There is simple, but expensive problem in cryptography is Modular Exponentiation which can be written as

Calculate y = (p^n) mod (2^32) where p is a prime number and n is a large integer.

Using BigInteger

You can use the obvious way using BigInteger.

BigInteger answer = BigInteger.valueOf(prime)
                              .pow(number)
                              .mod(BigInteger.valueOf(2).pow(32));

This works, but is very expensive for large numbers.  This can take minutes/hours for large number.

Fortunately BigInteger has a method which is useful in the situation. Instead of generating a very large numebr only to modulus back into a smaller one, it has a combined method called

BigInteger modPow(BigInteger power, BigInteger mod) 

This method is much faster and can take milli-seconds.

Using Overflow

If you look at the magic number 2^32 this appears to be an odd choice at first.  The trick is to realise this is the same as & 0xFFFFFFFFL or just keeping the lowest 32-bits. One type does this naturally which is the int type.  Technically, it should be an unsigned int but Java doesn't support this. 

Fortunately the difference can be compensated for by masking the result.

    public static long powMod2_32(int prime, int number) {
        int answer2 = 1;
        int p = prime;
        for (int n = number; n > 0; n >>>= 1) {
            if ((n & 1) != 0)
                answer2 *= p;
            p *= p;
        }
        return answer2 & 0xFFFFFFFFL;
    }
This only calculates the lowest 32-bit by making use of the fact it overflows (discarding any higher bits)  It also calculates squares of squares so it doesn't need to iterate each power, as does BigInteger.  The main gain is using a very efficient type and not needing to do anything extra to get the "mod 2^32"

Performance Comparison

The BigInteger.modPow is fast, but using the loop above is much faster.  For this test, the warmed up results look like

True answer 4,231,348,777 took 5.169 μs, quick answer 4,231,348,777 took 0.051 μs
True answer 1,807,631,477 took 4.922 μs, quick answer 1,807,631,477 took 0.051 μs
True answer 3,579,038,417 took 3.974 μs, quick answer 3,579,038,417 took 0.052 μs
True answer 3,923,287,037 took 4.679 μs, quick answer 3,923,287,037 took 0.051 μs
True answer 2,169,903,033 took 5.381 μs, quick answer 2,169,903,033 took 0.051 μs

Summary

Normally, you would not want overflows and you need to ensure they are avoided, but in this cause the original algorithm was designed to exploit it, and it can make a big difference.