## 5 Basic Algorithm of Montgomery Multiplication in Minimally Redundant RNS
At the same time, the integer \(\widehat{C}\in\mathbb{Z}_{p}\) is calculated using the equality_  
\[\widehat{C}=C^{\prime\prime}-\mathrm{CMP}(C^{\prime\prime},p)p, \tag{36}\]  
A similar result can also be obtained in the case when \(A\) and \(B\) belong to the range \(\mathbb{Z}_{2p}\). Therefore, by analogy to (32), the following inequality  
\[C^{\prime\prime}<\left(4p^{2}+pM_{l}\right)/M_{l}=p(1+4p/M_{l}) \tag{37}\]  
leads to the condition  
\[M_{l}>4p. \tag{38}\]Hence, the following statement is true. 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}{ll}4p<M_{l},\\ 2p<M_{k}/M_{l},\end{array} \right. \tag{39}\]  
and let the operands \(A\), \(B\) of the multiplicative operation \(\widehat{C}=\left|ABM_{l}^{-1}\right|_{p}\) belong to the ring \(\mathbb{Z}_{2p}=\{0,1,\ldots,2p-1\}\). Then, the integer \(C^{\prime\prime}\) (see (21)) also belongs to the ring \(\mathbb{Z}_{2p}\). At the same time, the integer \(\widehat{C}\) is calculated according to (36). Based on the optimized Montgomery multiplicative scheme (31) in minimally redundant RNS, an algorithm for multiplication over a large modulus is synthesized. This algorithm has a tabular configuration and possesses all the fundamental advantages of minimally redundant residue arithmetic, which most appear when operating in the ranges of large numbers. The developed algorithm is suitable for both software realization and implementation using parallel modular computational structures with a multiprocessor architecture. Considering the aforementioned discussion, the implementation of MM in a minimally redundant RNS can be formally presented as Algorithm 1. This algorithm's key distinguishing feature is its inherent suitability for using lookup table techniques. In this case, the required set of lookup tables is generated during the preliminary stage, ensuring the minimization of the labor intensity of the real-time MM implementation. ```
Input:\(A=(\alpha_{0},\alpha_{1},\ldots,\alpha_{k})\), \(B=(\beta_{0},\beta_{1},\ldots,\beta_{k})\), \(p=(\tau_{0},\tau_{1},\ldots,\tau_{k})=\left\langle p_{t},p_{l-1},\ldots,p_{1}\right\rangle\) Output:\(\widehat{C}=\left|ABM_{l}^{-1}\right|_{p}\)
1\(C=AB=(\gamma_{0},\gamma_{1},\ldots,\gamma_{k})\), \(\gamma_{i}=\left|\alpha_{i}\beta_{i}\right|_{m_{i}}(i=0,1,\ldots,k)\)
2\(X=\left|CY\right|_{M_{l}}=(\chi_{0},\chi_{1},\ldots,\chi_{l})\), \(\chi_{i}=\left|\gamma_{i}\right|-\left.\tau_{i}^{-1}\right|_{m_{i}}\right|_{m _{i}^{\prime}}(i=0,1,\ldots,l)\)
3\(\rho_{l}(X)=\widehat{p}_{l}(X)+\delta_{l}(X)\)
4\((\chi_{l+1},\chi_{l+2},\ldots,\chi_{k})=\text{BEX}(X;\mathbb{M}_{1},\mathbb{ M}_{2})\)
5\(C^{\prime}=C+Xp=(\gamma_{0}^{\prime},\gamma_{l+1}^{\prime},\ldots,\gamma_{k}^{ \prime})\), \(\gamma_{j}^{\prime}=\left|\gamma_{j}+\left|\chi_{j}\pi_{j}\right|_{m_{j}} \right|_{m_{j}}(j=0,l+1,l+2,\ldots,k)\)
6\(C^{\prime\prime}=C^{\prime}/M_{l}=(\gamma_{0}^{\prime\prime},\gamma_{l+1}^{ \prime\prime},\ldots,\gamma_{k}^{\prime\prime})\), \(\gamma_{j}^{\prime\prime}=\left|M_{l}^{-1}\gamma_{j}^{\prime}\right|_{m_{j}}( j=l+1,l+2,\ldots,k)\)
7\(\rho_{n}(C^{\prime\prime})=\widehat{\rho}_{n}(C^{\prime\prime})+\delta_{n}(C^{ \prime\prime})\)
8\((\gamma_{1}^{\prime\prime},\gamma_{2}^{\prime\prime},\ldots,\gamma_{l}^{ \prime\prime})=\text{BEX}(C^{\prime\prime};\mathbb{M}_{2},\mathbb{M}_{1})\)
9\(\langle c_{l}^{\prime\prime},c_{l-1}^{\prime\prime},\ldots,c_{l}^{\prime 1} \rangle=\text{RC}(C^{\prime\prime})\)
10\(Q=\text{CMP}(C^{\prime\prime},p)\)
11\(\widehat{C}=C^{\prime\prime}-Qp=(\widehat{\gamma}_{0},\widehat{\gamma}_{1}, \ldots,\widehat{\gamma}_{k})\), \(\widehat{\gamma}_{j}=\left|\gamma_{j}^{\prime\prime}-Q\pi_{j}\right|_{m_{j}}( j=0,1,\ldots,k)\)
```  
**Algorithm 1**Montgomery multiplication in minimally redundant RNS