4
$\begingroup$

In Montgomery reduction, when calculating $a \times b \mod N$, it is required that $a \lt N$ and $b \lt N$.
I think $0 \le T \lt N \times R$ is enough for the Montgomery Reduction.

Rationale:

Let $a' = a \times R \mod N$,
let $b' = b \times R \mod N$, and
let $T = a' \times b'$.

Then $T \times R^{-1} = ((T + ((T \times (-N^{-1}) \mod R) \times N) / R) \mod N$.

$T \lt N^{2} \lt N \times R$ as $R \gt N$. Also remainder of $\mod R \lt R$, so $(T + ((T \times (-N^{-1}) \mod R) \times N)/ R \lt (N \times R + R \times N)/R = 2 \times N$.

As such, $a$ and $b$ can be greater than $N$. Is that correct? If it isn´t, what´s wrong with my rationale?

$\endgroup$
1
$\begingroup$

Looks like misunderstanding to me: you are asking about Montgomery reduction but your example is about Montgomery multiplication.

Montgomery reduction inputs a number in range $[0..NR-1]$ and outputs a number in range $[0..N-1]$, where $R$ - auxiliary Montgomery modulus.

Montgomery multiplication inputs two numbers $A$ and $B$ in range $[0..N-1]$ and outputs a number in range $[0..N-1]$

Internally, Montgomery multiplication is standard integer multiplication followed by Montgomery reduction; so, formally it is possible to apply Montgomery multiplication to any numbers $A \ge 0$ and $B \ge 0$ such that $AB \le NR-1$. Since $R \gt N$, this is weaker requirement than $0 \le A \le N-1$ and $0 \le B \le N-1$, but I doubt this possibility makes practical sense.

$\endgroup$
0
$\begingroup$

Of course because all the calculation are done in residue Class modulo N. Example: $a^{'}=a * R \; mod \; N =(a+ \lambda .N)*R \; mod \; N$

Then the value of T is invariant modulo N.

$\endgroup$
  • $\begingroup$ Not a and b must be smaller then n, but a' and b' must be smaller then n. $\endgroup$ – user27950 Oct 23 '15 at 17:51

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.