Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
Does this have anything specifically to do with cryptography? It might be better suited for Stack Overflow. –  B-Con Nov 13 '12 at 20:29
1  
Can you not just do normal multiplication to compute the square of the constant? –  mikeazo Nov 14 '12 at 0:26
    
@B-Con: I'd say as much as Montgomery multiplication has: I'm not sure if there are many other settings where one wants to compute modular exponentiations with a modulus of 4096 bits :D –  bob Nov 14 '12 at 8:09
1  
@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. Nov 14 '12 at 8:51
2  
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 Nov 14 '12 at 9:39
show 10 more comments

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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