I have Montgomery exponentiation working, but it's working quite slow. I suspect there are two reasons for this - I implemented it bit size instead of word size (I didn't realize at the time that software implementation should use word size).
The second is how I select R. Given a modulus N with bit length n, I'm calculating R by raising 2 to the power of the bit length of N, n. i.e. This is way all the examples I've seen use, but they all use small numbers. Every number I'm dealing with here has at least 1024 bits.
BigInteger R = new BigInteger("2").pow(n.bitLength());
I suspect this might be why my Montgomery is running slower than my Right-To-Left binary implementation - can anyone give me a more efficient way of selecting r? (In as simple English as possible please!)
Edit - the full code is at - http://codereview.stackexchange.com/questions/18199/optimization-of-exponentiation if anyone want to have a look at it.