1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Do you mean $2^l$ instead of $n^l?$ $\endgroup$ – gammatester Nov 3 '18 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.