Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
In Montgomery Reduction, we need to compute $z = x y \text{ mod } N$ and the Montgomery Reduction of $x$ is $xR^{-1}$.
This is a cross question with math.stackexchange.
First of all, The Montgomery's Reduction algorithm requires that $\operatorname{GCD}(n,R)=1$ . This requirement is satisfied iff $n$ is odd.
The $R$ is chosen as $2^l$ where $ 2^{l-1} \leq n < 2^{l}$.
For $x < n$ the $n$-residue with respect to $R$ is defined as;
$$ x' = x \cdot r \bmod n$$ than the set
$$\{i \cdot R \bmod n\;|\; 0 \leq i \leq n-1 \}$$ is a complete residue system, that is, it contains all the numbers between $0$ and $n-1$.
The selection of $R$ is the smallest bound.
- Why should the choice of $R$ be $2^l$ where $l$ is the length of $N$ to the base $2$?
Montgomery Reduction converts arbitrary division into shift operations. Therefore $2^l$ is a good choice for computers, we have to shift $l$ bits.
- Why cannot we have a larger $R$?
It won't be effective since you will have more unnecessary shiftings due to a larger $R$.
note: if $R<n$ than this will not work.
