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.

Comments

  1. Very interesting idea. Thank you for article.

    A bit offtopic:
    I'm confused by introduction. Actually, modular exponentiation (that you optimized by overflow) is not problem in cryptography, but inverse operation (discrete logarithm) is really challenge. And it is problem doesn't because exponentiation too much expensive. I mean acceleration of exponentiation can accelerate bruteforce, but can't resolve the problem, just because the solution is bruteforce :)

    ReplyDelete
  2. From wikipedia: "Modular exponentiation is a type of exponentiation performed over a modulus. It is particularly useful in computer science, especially in the field of cryptography."

    I can see that discrete logarithm, is serious problem, but this doesn't use modularisation. Perhaps you are saying that this the real challenge.

    ReplyDelete
  3. It is really used and your optimization really useful too :). But it is not a problem in the field of cryptography.

    Wiki has very poor description of discrete logarithm problem. Specifically in cryptography the elements of logarithm are members of finite cyclic group hence modularisation involved in problem. As a trivial example you can look at Diffi-Hellman algorithm. Security of this algorithm is based on discrete logarithm problem with modularisation.

    ReplyDelete
  4. Perhaps I've perceived wrong word "problem". Sorry if it so :) I'm used to that in cryptography this word means very complicated issues such as the prime factorisation, discrete logarithm etc.

    ReplyDelete

Post a Comment

Popular posts from this blog

Low Latency Microservices, A Retrospective

Unusual Java: StackTrace Extends Throwable

System wide unique nanosecond timestamps