Efficient setup for a Montgomery multiplication

Montgomery described an efficient method to compute a modular multiplication. This works by using a special constant $R$ and assumes the inputs $a$ and $b$ have been made into a special representation (residues $aR\mod N$ and $bR\mod N$) and produces the value $abR^{-1}\mod N$. Thus to pursue the computations, one needs the value $ab$ to be also in the special representation, which requires an additional (Montgomery) multiplication with the constant $R^2\mod N$.

This is especially useful to compute modular exponentiations with a large modulus $N$ and a big exponent such as in RSA.

Every step such as computing the special representation of $a$ and $b$ are costly, and so is the computation of $R^2\mod N$ (note that it has to be computed once, but still is costly).

What are the different ways to do the computation of $R^2 \mod N$ efficienty?

• Does this have anything specifically to do with cryptography? It might be better suited for Stack Overflow. Commented Nov 13, 2012 at 20:29
• Can you not just do normal multiplication to compute the square of the constant? Commented Nov 14, 2012 at 0:26
• @mikeazo: The idea of using Montgomery multiplication is also to avoid implementing long division (quite costly in HW, and not as easy as one might think in SW).
– j.p.
Commented Nov 14, 2012 at 8:51
• I challenge the widely stated opinion that Montgomery modular multiplication is significantly more efficient than regular modular multiplication: the number of elementary multiply-and-add for $b$-word numbers is $o(2⋅b^2)$ in both cases. The naive implementation of regular modular multiplication makes more memory accesses, but that can be fixed. Key advantages of Montgomery multiplication are elsewhere: quotient estimation never errs, so there is no necessity to recover from that, which may creates a side-channel leakage.
– fgrieu
Commented Nov 14, 2012 at 9:39
• @jug: I fully agree with both of your comments in this thread. In hardware, Montgomery has advantages, and is (thus) used in many hardware modexp. I was answering to GregS, and his "Actual experiments for most processors and implementations seem to show the Montgomery is a big win against the naive algorithm"; I'm more in agreement with the opinion on page 61 of Modern Computer Arithmetic 0.5.9.
– fgrieu
Commented Nov 23, 2012 at 16:05

The usual way is to calculate $2^k R \bmod N$ for a small divisor $k$ of $l$ where $R = 2^l$ and use Montgomery multiplication in a Square-and-Multiply algorithm. This does require a division, but as $R$ is usually chosen to be just a little bit longer than $N$, the division doesn't have to be optimized much.
But you should also consider the fact that in some occasions (like RSA key generation) one can do also without knowing $R^2 \bmod N$. You neither have to Montgomery transform the random bases for a Fermat or Miller-Rabin test nor a number you want to invert using Fermat's little theorem (in the second case just Montgomery multiply with $1$ afterwards).