## 5 Basic Algorithm of Montgomery Multiplication in Minimally Redundant RNS  
According to the above, the implementation of the Montgomery multiplicative scheme (11) using minimally redundant RNS results in the following operational sequence:  
\[\big{\langle}C=AB=(\gamma_{0},\gamma_{1},\ldots,\gamma_{k});\ \ X=|CY|_{M_{i}}=(\chi_{0},\chi_{1},\ldots,\chi_{l});\] \[(\chi_{l+1},\chi_{l+2},\ldots,\chi_{k})=\text{BEX}(X;\mathbb{M}_{1},\mathbb{M}_{2});\ \ C^{\prime}=C+Xp=(\gamma_{0}^{\prime},\gamma_{l+1}^{ \prime},\ldots,\gamma_{k}^{\prime});\] \[C^{\prime\prime}=C^{\prime}/M_{l}=(\gamma_{0}^{\prime\prime}, \gamma_{l+1}^{\prime\prime},\ldots,\gamma_{k}^{\prime\prime});\ \ (\gamma_{1}^{\prime\prime},\gamma_{2}^{\prime\prime},\ldots, \gamma_{l}^{\prime\prime})=\text{BEX}(C^{\prime\prime};\mathbb{M}_{2}, \mathbb{M}_{1});\] \[\widehat{C}=C^{\prime\prime}-\text{CMP}(C^{\prime\prime},p)=( \widehat{\gamma}_{0},\widehat{\gamma}_{1},\ldots,\widehat{\gamma}_{k})\big{\rangle}. \tag{31}\]A necessary and sufficient correctness condition for the two-stage process of calculating \(C^{\prime\prime}=(\gamma_{0}^{\prime\prime},\gamma_{1}^{\prime\prime},\ldots, \gamma_{k}^{\prime\prime})\), according to (22), (23) and (29), for \(C=AB\in\mathbb{Z}_{M_{k}}\), is that the numbers \(X\) and \(C^{\prime\prime}\) should belong to the range \(\mathbb{Z}_{M_{n}}=\{0,1,\ldots,M_{n}-1\}\) with respect to the moduli \(m_{l+1},m_{l+2},\ldots,m_{k}\). Since the inequality \(0\leq C^{\prime\prime}=C^{\prime}/M_{l}<M_{n}\) implies the inequality \(0\leq C^{\prime}<M_{k}\), the condition \(C^{\prime\prime}\in\mathbb{Z}_{M_{n}}\) guarantees the fulfillment of the condition \(C^{\prime}\in\mathbb{Z}_{M_{k}}\). Now, let us explore the necessary conditions for \(m_{1},m_{2},\ldots,m_{k}\) and \(p\) to ensure that \(X,C^{\prime\prime}\in\mathbb{Z}_{M_{n}}\). Let \(A,B\in\mathbb{Z}_{p}=\{0,1,\ldots,p-1\}\). Since, according to (12), \(X<M_{l}\), then from (21) we obtain the inequality  
\[C^{\prime\prime}<(p^{2}+pM_{l})/M_{l}=p(1+p/M_{l}). \tag{32}\]  
From (32), it follows that \(C^{\prime\prime}\in\mathbb{Z}_{2p}=\{0,1,\ldots,2p-1\}\) only when \(p/M_{l}<1\). On the other hand, the numbers \(X\) and \(C^{\prime\prime}\) should be the elements of the range \(\mathbb{Z}_{M_{n}}\) concerning moduli \(m_{l+1},m_{l+2},\ldots,m_{k}\). Therefore, taking into account that \(X<M_{l}\) and \(C^{\prime\prime}<2p\), this requirement leads to the following inequalities:  
\[M_{l}<M_{k}/M_{l} \tag{33}\]  
and  
\[2p<M_{k}/M_{l}. \tag{34}\]  
Thus, in the case when \(A,\ B\in\mathbb{Z}_{p}\) and \(C^{\prime\prime}\in\mathbb{Z}_{2p}\), the correctness of the proposed MM scheme is ensured by the conditions (33) and (34). As already noted, the magnitude comparison of the integers \(C^{\prime\prime}\) and \(p\) is performed using MRS, resulting in \(\mathrm{CMP}(C^{\prime\prime},p)\) (see (10)). Therefore, the correctness of the reverse conversion \(C^{\prime\prime}<2p\) is ensured by using the RNS number range that includes the range \(\mathbb{Z}_{2p}\). As follows from (33) and (34), the number range \(\mathbb{Z}_{M_{k}}\) significantly exceeds the range \(\mathbb{Z}_{2p}\). To determine the integer factor \(Q\), according to (10), it is sufficient to use the truncated RNS defined by the moduli set \(\mathbb{M}_{1}\) with the number range \(\mathbb{Z}_{M_{l}}\). Based on the above, the following statement is true. **Theorem 1**. : _Let the moduli of the sets \(\mathbb{M}_{1}=\{m_{1},m_{2},\ldots,m_{l}\}\) and \(\mathbb{M}_{2}=\{m_{l+1},m_{l+2},\ldots,m_{k}\}\), together with the modulus \(p\) meet the conditions_  
\[\left\{ \begin{array}{l}M_{l}<M_{k}/M_{l},\\ 2p<M_{k}/M_{l},\end{array} \right. \tag{35}\]  
_and let the operands \(A\), \(B\) of the multiplicative operation \(\widehat{C}=\left|ABM_{l}^{-1}\right|_{p}\) belong to the ring \(\mathbb{Z}_{p}=\{0,1,\ldots,p-1\}\). Then, the integer \(C^{\prime\prime}\) (see (21)) is an element of the ring \(\mathbb{Z}_{2p}=\{0,1,\ldots,2p-1\}\).