Why should $a,b < N$ for Montgomery Reduction?

Question

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?

Answer 1

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.

Answer 2

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.