Editing Montgomery modular multiplication (section)

== Interpretation via the Chinese Remainder Theorem <ref>{{cite arXiv | eprint=2402.00675 | last1=Xu | first1=Guangwu | last2=Jia | first2=Yiran | last3=Yang | first3=Yanze | title=Chinese Remainder Theorem Approach to Montgomery-Type Algorithms | date=2024 | class=cs.CR }}</ref> ==

Given the modulus {{mvar|N}} and the Montgomery radix {{mvar|R}} used in a Montgomery reduction, consider the [[Modular arithmetic|residue ring]]

<math>\mathbb{Z}/(NR)\mathbb{Z}\;\cong\;\mathbb{Z}/N\mathbb{Z}\;\times\;\mathbb{Z}/R\mathbb{Z},</math>

an [[isomorphism]] that follows from the [[Chinese remainder theorem|Chinese Remainder Theorem (CRT)]].

=== CRT reconstruction for an intermediate product ===
For an integer <math>T</math> with <math>0 \le T < NR</math> (as is typical when <math>T</math> arises from multiplying two residues), take its reductions

<math>T_N = T \bmod N, \qquad

T_R = T \bmod R .

</math>

The [[Chinese remainder theorem|CRT]] gives the explicit reconstruction formula

<math>T \equiv

T_N\bigl(R^{-1} \bmod N\bigr)\,R

\;+

T_R\bigl(N^{-1} \bmod R\bigr)\,N

\pmod{NR}.

</math>

Because the right-hand side is already taken modulo <math>NR</math>, this may also be written as

<math>T \equiv

\bigl(T_N R^{-1} \bmod N\bigr) R

\;+

\bigl(T_R N^{-1} \bmod R\bigr) N

\pmod{NR}.

</math>

Both summands lie in the half‑open interval <math>[0,NR)</math>:

<math>0 \le \bigl(T_N R^{-1}\bmod N\bigr) R < NR,\qquad

0 \le \bigl(T_R N^{-1}\bmod R\bigr) N < NR .

</math>

Hence, as '''integer''' equations (not merely congruences) we have

<math>T =

\bigl(T_N R^{-1} \bmod N\bigr) R

\;+

\bigl(T_R N^{-1} \bmod R\bigr) N ,

</math>

or,

<math>T + NR =

\bigl(T_N R^{-1} \bmod N\bigr) R

\;+

\bigl(T_R N^{-1} \bmod R\bigr) N .

</math>

=== Isolating the term containing T mod N ===
To solve for <math>T_N</math>, isolate the first summand:

<math>\bigl(T_N R^{-1} \bmod N\bigr) R

=

\begin{cases}

T - \bigl(T_R N^{-1} \bmod R\bigr) N, \\

T + NR - \bigl(T_R N^{-1} \bmod R\bigr) N .

\end{cases}

</math>

Every quantity above is an integer, and the left‑hand side is a multiple of <math>R</math>; therefore each right‑hand side is divisible by <math>R</math>. Dividing by <math>R</math> yields

<math>T_N R^{-1}\bmod N
=\begin{cases}

\dfrac{T - \bigl(T_R N^{-1} \bmod R\bigr) N}{R},\\[8pt]

\dfrac{T + NR - \bigl(T_R N^{-1} \bmod R\bigr) N}{R}

\,=\,\dfrac{T - \bigl(T_R N^{-1} \bmod R\bigr) N}{R} + N .

\end{cases}

</math>

=== Resulting relations ===
Consequently,

<math>\dfrac{T - \bigl(T_R N^{-1} \bmod R\bigr) N}{R}

=

\begin{cases}

T_N R^{-1}\bmod N,\\

T_N R^{-1}\bmod N \; + \; N .

\end{cases}



</math>

This gives two key facts:

* '''Congruence'''
<math>  \frac{T - \bigl(T_R N^{-1}\bmod R\bigr) N}{R}
\;\equiv\;
T_N R^{-1}
\pmod{N}.</math>

* '''Numeric bound'''
<math> 
  0 \;\le\;
  \frac{T - \bigl(T_R N^{-1}\bmod R\bigr) N}{R}
  \;<\;
  2N.
  
</math>

Therefore, by reducing

<math>
\frac{T - \bigl(T_R N^{-1}\bmod R\bigr) N}{R}
</math>

once more modulo {{mvar|N}}, one obtains the non‑negative residue representing <math>T_{N} R^{-1}\bmod N</math>.