Modular exponentiation optimisation in Java
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&amp;oldid=517653653#Right-to-left_binary_method
    BigInteger result = BigInteger.ONE;
    while (exponent.compareTo(BigInteger.ZERO) &gt; 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)