Optimization of exponentiation

Question

I'm writing some crypto code, and as part of it, we have to implement modular exponentiation. I have it working, both with the right-to-left binary method and with the Montgomery formula.

While they both work, the Montgomery calculations take three times longer than the right-to-left binary method. This is extremely frustrating, as I worked out the right-to-left in an afternoon, but it's taken me three days solid work to figure out the Montgomery. I thought it would be faster, so I'm guessing it's my implementation - three different function calls are used to work it out.

Here is the code, if anyone can see anything that would speed it up I'd be delighted to hear it.

First I needed a function to get the values for Extended Euclid -

private static BigInteger[] extendedEuclid(BigInteger p, BigInteger q) {

if(q.compareTo(BigInteger.ZERO) == 0)
    return new BigInteger[] {p, BigInteger.ONE, BigInteger.ZERO};

BigInteger[] vals = extendedEuclid(q, p.mod(q));
BigInteger d = vals[0];
BigInteger a = vals[2];
BigInteger divBit = p.divide(q);
BigInteger mulBut = divBit.multiply(vals[2]);   
BigInteger b = vals[1].subtract(mulBut);
return new BigInteger[] {d, a, b};
}

This works but calculates value I never need - all I use is values[1] but to get it I need to calculate the others, I think?

Next we have the helper function monPro :

private static BigInteger monPro(BigInteger aBar, BigInteger bBar, BigInteger r, BigIntegernPrime, BigInteger n) { 

    BigInteger t = aBar.multiply(bBar);
    BigInteger m = (t.multiply(nPrime)).mod(r);
    BigInteger u = (m.multiply(n).add(t)).divide(r);

    if(u.compareTo(n) >= 0)
        return u.subtract(n);
    else return u;
}

This is needed to use the final function, modExp -

private static BigInteger modExp(BigInteger M, BigInteger e, final BigInteger n) {
BigInteger r = new BigInteger("2").pow(n.bitLength());
BigInteger[] values = extendedEuclid(r, n);
BigInteger rInverse = values[1].mod(n);
BigInteger mBar = M.multiply(r).mod(n);
BigInteger xBar = new BigInteger("1").multiply(r).mod(n);
BigInteger nPrime = n.negate().modInverse(r);

for(int i = e.bitLength() -1 ; i >= 0 ; i--) {
    xBar = monPro(xBar, xBar, r, nPrime, n);
    if (e.testBit(i) == true) 
        xBar = monPro(mBar, xBar, r, nPrime, n);
    }
    BigInteger returnValue = monPro(xBar, BigInteger.ONE, r, nPrime, n);
    return returnValue;
    }
}

I'm almost certain the running time is due to the amount of time the actual modExp functon calls monPro. Euclid is only called once so I can't see that being the huge deal, I could be wrong. Anyway, any tips or pointers much appreciated, this has turned out to be an extremely frustrating exercise (optimize for three days and slow it down by a factor of three....booooooo!)

PS - I'm not allowed use the BigInteger function modPow.

Answer 1

There are two points where you can improve the performance. This is more related to the algorithm itself, but I guess the answer fits better here than in crypto.SE...

1. When computing m and u, you are using mod(r) and divide(r). But since r is a power of 2, these are just a bitwise and (with r - 1) and a right shift (by n.bitLength()), which should be much faster. It also helps reducing t modulo r (also using and) before multiplying by nPrime.
2. Montgomery works better at the word level. If n has w words, then your code takes 2 * (w^2) word multiplications when computing m and u, but could take w^2 + w when using word-level Montgomery. So if you really need speed, you'll need to use an array of integers instead of BigInteger.

Answer 2

Not really an optimization note but I'd be much cleaner if you'd use a separate object to store the result value instead of the BigInteger array. Its keys are magic numbers currently. They could be named fields in the result object. It would also remove the risk of creating arrays with more or less values than required and the risk of accessing invalid indexes.