Tag Info

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

Montgomery multiplication makes sense only with word sizes. If your word size is $w$ (e.g. $w = 32$ if you have 32-bit words), then $R = 2^{kw}$ for some integer $k$; you choose $k$ as small as possible, given that you must have $R \geq N$. In plain words, if your modulus $N$ has size $n$ bits, then you look for the next multiple of $w$. For a 1024-bit ...