## 4 Realization of Montgomery Modular Multiplication in Minimally Redundant RNS  
Let a primary Residue Number System (RNS) be defined on the set \(\mathbb{M}=\{m_{1},m_{2},\ldots,m_{k}\}\) of pairwise relatively prime odd moduli \(m_{i}\ (m_{i}>2,\ i=1,2,\ldots,k;\ k\geq 2)\), with an additional modulus \(m_{0}=2\). Consequently, the moduli set \(\{m_{0},m_{1},\ldots,m_{k}\}\) forms a minimally redundant RNS. The effective number range is given by the ring \(\mathbb{Z}_{M_{k}}=\{0,1,\ldots,M_{k}-1\}\). Let the operands \(A\), \(B\), and modulus \(p\) be represented by their minimally redundant residue codes:  
\[A=(\alpha_{0},\alpha_{1},\ldots,\alpha_{k}),\quad B=(\beta_{0},\beta_{1}, \ldots,\beta_{k}),\quad p=(\pi_{0},\pi_{1},\ldots,\pi_{k}),\]  
where \(\alpha_{i}=|A|_{m_{i}},\quad\beta_{i}=|B|_{m_{i}},\quad\pi_{i}=|p|_{m_{i}}, \quad\text{and}\quad i=0,1,\ldots,k\). The complete moduli set \(\mathbb{M}\) is a sum of moduli sets \(\mathbb{M}_{1}=\{m_{1},m_{2},\ldots,m_{l}\}\) and \(\mathbb{M}_{2}=\{m_{l+1},m_{l+2},\ldots,m_{k}\}\). Here, the auxiliary modulus \(S\) is defined as the product of the moduli in the set \(\mathbb{M}_{1}\):  
\[S=M_{l}=\prod_{i=1}^{l}m_{i},\quad\text{where}\quad 1<l<k.\]Since the multiplicative inversion \(Y=\left|p^{-1}\right|_{M_{l}}\) (see (11)) belongs to the ring \(\mathbb{Z}_{M_{l}}=\{0,1,\ldots,M_{l}-1\}\), it is uniquely represented in a minimally redundant residue code as follows:  
\[(\xi_{0},\xi_{1},\ldots,\xi_{l}),\]  
where \(\xi_{i}=\left|-\pi_{i}^{-1}\right|_{m_{i}}\) for \(i=0,1,\ldots,l\). Similarly, the number \(X=\left|CY\right|_{M_{l}}\) (see (11)) is represented in a minimally redundant residue code with respect to \(\mathbb{M}_{1}\):  
\[X=(\chi_{0},\chi_{1},\ldots,\chi_{l})=\left(\left|\gamma_{0}\xi_{0}\right|_{m_ {0}},\left|\gamma_{1}\xi_{1},\right|_{m_{1}},\ldots,\left|\gamma_{l}\xi_{l} \right|_{m_{l}}\right), \tag{12}\]  
where \(\chi_{i}=\left|X\right|_{m_{i}}\gamma_{i}=\left|\alpha_{i}\beta_{i}\right|_{m _{i}}\) (\(i=0,1,\ldots,l\)). Following (11), we compute the residue code of \(C^{\prime}=C+Xp\) with respect to the complete moduli set \(\mathbb{M}\). Before proceeding, it is necessary to extend the residue code (12) to the moduli in \(\mathbb{M}_{2}\). Base extension is one of the most difficult non-modular operations in RNS arithmetic. Its implementation usually uses the rank form (1) [12; 13; 14; 15; 16]. Following (1), the number \(X\) with respect to \(\mathbb{M}_{1}\) is represented by the following:  
\[X=\sum_{i=1}^{l}M_{i,l}\chi_{i,l}-\rho_{l}(X)M_{l}, \tag{13}\]  
where, based on the theorem for rank calculation in minimally redundant RNS [25; 27],  
\[\rho_{l}(X)=\widehat{\rho}_{l}(X)+\delta_{l}(X), \tag{14}\]  
with \(\widehat{\rho}_{l}(X)\) as the inexact rank of the number \(X\), and \(\delta_{l}(X)\) as a two-valued rank correction:  
\[\widehat{\rho}_{l}(X)\in\mathbb{Z}_{l}=\{0,1,\ldots,l-1\},\quad\delta_{l}(X) \in\mathbb{Z}_{2}=\{0,1\}.\]  
The inexact rank \(\widehat{\rho}_{l}(X)\) is calculated as follows:  
\[\widehat{\rho}_{l}(X)=\left|\left.\frac{1}{m_{l}}\sum_{i=1}^{l}R_{i,l}(\chi_{ i})\right.\right|, \tag{15}\]  
where  
\[R_{i,l}(\chi_{i})=\left|-\frac{1}{m_{i}}\Big{|}M_{i,l-1}^{-1}\chi_{i}\Big{|}_ {m_{i}}\right|_{m_{l}}\ (i\
eq l), \tag{16}\]  
\[R_{l,l}(\chi_{l})=\left|M_{l-1}^{-1}\chi_{i}\right|_{m_{i}}, \tag{17}\]  
with \(M_{l-1}=M_{l}/m_{l}\) and \(M_{i,l-1}=M_{l-1}/m_{i}\) (\(i=1,2,\ldots,l-1\)). Similarly, the rank correction \(\delta_{l}(X)\) is computed using trivial addition operations modulo \(m_{0}=2\):  
\[S=M_{l}=\prod_{i=1}^{l}m_{i},\quad\text{where}\quad 1<l<k.\]0  
where \(\chi_{i,l}^{(0)}=\left|\chi_{i,l}\right|_{m_{0}}\), \(\widehat{\rho}_{l}^{(0)}=\left|\widehat{\rho}_{l}(X)\right|_{m_{0}}\), and \(i=1,2,\ldots,l\)[25; 27].