# 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 < 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 than this will not work.

• Do you mean $2^l$ instead of $n^l?$ Nov 3 '18 at 13:33