montgomery multiply mod n

 R = 2^k   where 2^k > n

montgomeryMultiply(x, y) = x * y * R^-1



addition?

 xR + yR = (x + y)R

totally works to just add the montgomery representations, except on overflow?

x + y >= n, ...?

on actual overflow of the addtion xR + yR, then we have computed (x + y)R - 2^k = (x + y - 1)R mod n

so we just need to add R mod n back in if there is a carry out.
Of course, that may entail another carry out (if R mod n is close to 2^k).

-Xrunhprof:cpu=samples

