# Tag Info

4

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

3

The conversion formula from twisted Edwards to Montgomery form is: $$x_{mont} = \frac{X_{mont}}{Z_{mont}}= \frac{1+y_{ed}}{1-y_{ed}} = \frac{1+\frac{Y_{ed}}{Z_{ed}}}{1-\frac{Y_{ed}}{Z_{ed}}} = \frac{Z_{ed}+Y_{ed}}{Z_{ed}-Y_{ed}}$$ If you want the affine $x_{mont}$, you need to compute the inversion. But if you just need $X_{mont}$ and $Z_{mont}$ you can ...

2

As I said above, I feel the question is bit off-topic here. However, there does not seem to be too good a place in SE for questions that combine mathematics and programming on VHDL, where target is obviously something cryptography related. Most questions regarding FPGA are seen in electronics.stackexchange.com. Montgomery reduction in Wikipedia is useful ...

2

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

Only top voted, non community-wiki answers of a minimum length are eligible