Modular exponentiation optimisation in Java

Question

As part of an assignment in Cryptography I've been asked to write code that involves calculating modular exponentiation. The BigInteger modPow is not allowed in this case, we have to implement it ourselves.

I have the assignment working, but I think my modular exponentiation function is not the greatest in terms of run time. It's based on the right-to-left binary method. Here is it :

The algorithm calculates (a^b) mod c.

private static BigInteger modulo(BigInteger a, BigInteger b, BigInteger c) { 

    BigInteger x = BigInteger.ONE;
    final BigInteger TWO = new BigInteger("2", 16);

    while(b.compareTo(BigInteger.ZERO) > 0) {

        BigInteger compareVal = b.mod(TWO);
        if(compareVal.compareTo(BigInteger.ONE) ==0) { 
            x = (x.multiply(a)).mod(c);
        }

        a = (a.multiply(a)).mod(c);
        b = b.divide(TWO);
    }
    return x.mod(c);

}

However, that solution uses 2 comparisons, 2 multiplications and a division within the loop. Can anyone point me in the direction of something more efficient? I'm not looking for a specific answer here, maybe just some ideas. Googling modular exponentation doesn't yield much that's useful in this case, and when I time this algorithm it's performance is very poor.

Any direction or feedback would be hugely appreciated.

Answer 1

However, that solution uses 2 comparisons, 2 multiplications and a division within the loop.

You are doing 3 mod, they are not free, too (mod creates new internal copies and does a divide).

---

final BigInteger TWO = new BigInteger("2", 16);

I do not understand, why you parse 2 to basis 16? It does not change the result, but i suggest to use:

final BigInteger TWO = new BigInteger("2");

---

I assume here:

BigInteger compareVal = b.mod(TWO);
    if(compareVal.compareTo(BigInteger.ONE) ==0) { 

You want to check for oddnes. You can to this in constant time if you look at the last bit:

if (b.testBit(0)) // then it is odd

And you can get rid of this TWO

---

Instead of dividing by 2

b = b.divide(TWO);

You can shift:

b = b.shiftRight(1);

This has a better implementation.

---

The last mod for the return:

return x.mod(c);

is not needed:

return x;

---

and after all, you can choose better names and you could end up with:

private static BigInteger fastModPow(BigInteger base, BigInteger exponent, final BigInteger modulo) {
    // plan: exploit the binary representation of the exponent, see for example http://en.wikipedia.org/w/index.php?title=Modular_exponentiation&oldid=517653653#Right-to-left_binary_method
    BigInteger result = BigInteger.ONE;
    while (exponent.compareTo(BigInteger.ZERO) > 0) {
        if (exponent.testBit(0)) // then exponent is odd
            result = (result.multiply(base)).mod(modulo);
        exponent = exponent.shiftRight(1);
        base = (base.multiply(base)).mod(modulo);
    }
    return result.mod(modulo);
}

Small and meaningless test with base and exponent length of 50.000:
old: around 20s
new: around 1s
(Java: couple of ms)

If you want further optimization, you have to choose better algorithms. One little trick could be to look into the Java source code. If you are not allowed to use the Java method, noone forbids you to use the code inside?

(One last hint: If you do some non trivial algorithms, add a comment about it)

Answer 2

Just a quick note, not an optimization idea:

if(compareVal.compareTo(BigInteger.ONE) ==0) {  ... }

could be

if (compareVal.equals(BigInteger.ONE)) { ... }

which is a little bit easier to read. Furthermore, if you switch the objects it will be null-safe:

if (BigInteger.ONE.equals(compareVal)) { ... }

It does not throw NullPointerException when compareVal is null. (This is true for compareTo too, for example: BigInteger.ZERO.compareTo(b).)