Montgomery Reduction - Conditions on R In Montgomery Reduction, we need to compute $z = x y \text{ mod  } N$ and the Montgomery Reduction of $x$ is $xR^{-1}$.


Why should the choice of $R$ be $2^l$ where $l$ is the length of $N$ to the base $2$?
Why cannot we have a larger $R$?


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 &lt; 2^{l}$. 

For $x &lt; 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&lt;n$ than this will not work.