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.