Optimization of exponentiation

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);
BigIntege

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...

• 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.

• 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.

StackExchange Code Review Q#18199, answer score: 3