4
$\begingroup$

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?

Improve this question
$\endgroup$
15
  • $\begingroup$ Does this have anything specifically to do with cryptography? It might be better suited for Stack Overflow. $\endgroup$
    – B-Con
    Commented Nov 13, 2012 at 20:29
  • 1
    $\begingroup$ Can you not just do normal multiplication to compute the square of the constant? $\endgroup$
    – mikeazo
    Commented Nov 14, 2012 at 0:26
  • 1
    $\begingroup$ @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). $\endgroup$
    – j.p.
    Commented Nov 14, 2012 at 8:51
  • 2
    $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Commented Nov 14, 2012 at 9:39
  • 1
    $\begingroup$ @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. $\endgroup$
    – fgrieu ♦
    Commented Nov 23, 2012 at 16:05

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.