0
$\begingroup$

When we need to compute $z = xy \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$?

$\endgroup$
0
$\begingroup$

Theoretically $R$ needs to be such that $2^{l-1} < N < R = 2^l$. But practically $l$ is chosen to be multiples of CPU word so if 1 word is 32 bits and $l$ comes out to be 30 as per above equation, l will instead be chosen as 32 and then $R = 2^{32}$.
$2^l$ is chosen because in computers, it is efficient to do operations like multiplication, division, modulus with powers of 2.
Multiplication by $2^l$ is equivalent to shifting first $l$ bits to the left (and put zero at the place of shifted bits).
Division by $2^l$ is equivalent to shifting first $l$ bits to the right.
Taking modulo $2^l$ is equivalent to choosing the first $l$ bits only.

$\endgroup$

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.