## 6 Discussion
### Computational Costs of Proposed MM Algorithm
Comparing the numbers \(C^{\prime\prime}_{mrs}\) and \(p_{mrs}\) in the MRS requires \(l\) modular operations. In the final step, computing the modular code of the number \(\widehat{C}=C^{\prime\prime}-Qp\), taking into account the redundant modulus \(m_{0}\), requires \(k+1\) modular operations in a minimally redundant RNS, and \(k\) operations in a conventional RNS (see Equation (29)). Without loss of generality and for simplicity, let us assume that 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}\}\) are selected such that \(k=2l\). Under these assumptions, when employing a minimally redundant RNS, the total number of required modular operations, as derived from Table 1, is given by  
\[N_{1}(l)=\left(5l^{2}+21l\right)/2. \tag{40}\]  
In contrast, for a conventional non-redundant RNS, the required number of modular operations is  
\[N_{1}^{*}(l)=\left(7l^{2}+27l-28\right)/2. \tag{41}\]  
Hence, when \(A\),\(B\) and \(\widehat{C}\) belong to \(\mathbb{Z}_{p}\) (see Theorem 1), the reduction factor in computational complexity for implementing MM in a minimally redundant RNS, compared to a conventional non-redundant RNS, is given by  
\[C_{1}(l)=\frac{N_{1}^{*}(l)}{N_{1}(l)}=1+\frac{2l^{2}+6l-28}{5l^{2}+21l}. \tag{42}\]  
For instance, the computed values of \(C_{1}(l)\) for specific values of \(l\) are as follows: \(C_{1}(10)\approx 1.33\), \(C_{1}(15)\approx 1.36\), and \(C_{1}(20)\approx 1.37\). Furthermore, as \(l\) increases, the factor \(C_{1}(l)\) continues to grow, asymptotically approaching a limiting value of 1.40. It is well known that MM is primarily used for computing powers of natural numbers with respect to a large modulus \(p\):  
\[F(X,E,p)=\left|X^{E}\right|_{p}, \tag{43}\]  
where the numbers \(X\) and \(E\) are represented by their residue and binary codes, respectively: \(X=(\chi_{1},\chi_{2},\ldots,\chi_{k})\) and \(E=(e_{b-1},e_{b-2},\ldots,e_{0})_{2}\), where \(e_{b-1}\)=1 and \(b\) denotes the bit-length of \(E\). The well-known method for computing (43) relies on the multiplicative decomposition of the exponentiation function:  
\[F(X,E,p)=\left|X^{\sum_{j=0}^{b-1}e_{j}^{2}j^{2}}\right|_{p}=\left|X^{e_{0}}(X ^{e_{1}}(\ldots(X^{e_{b-2}}(X^{e_{b-1}})^{2})^{2}\ldots)^{2})^{2}\right|_{p}. \tag{44}\]  
All multiplicative operations in (44) are performed within the framework of scheme (11), which allows the reuse of previously computed results as subsequent operands. In this case, the fact that the number \(C^{\prime\prime}\) belongs to the ring \(\mathbb{Z}_{2p}\) when \(A,B\in\mathbb{Z}_{2p}\) is ensured by condition (39). Consequently, the correction operation (36) needs to be applied only at the final step of the computation in accordance with (44). In a minimally redundant RNS, the implementation of MM when \(A,B\), and \(C^{\prime\prime}\) belong to \(\mathbb{Z}_{2p}\) requires  
\[N_{2}(l)=2l^{2}+6l+3 \tag{45}\]  
modular operations (see Table 1). In contrast, in a conventional non-redundant RNS, the number of required modular operations is given by  
\[N_{2}^{\star}(l)=3l^{2}+9l-10. \tag{46}\]  
Thus, in the considered case, based on (45) and (46), the computational complexity reduction factor is expressed as  
\[C_{2}(l)=\frac{N_{2}^{\star}(l)}{N_{2}(l)}=1+\frac{l^{2}+3l-13}{2l^{2}+6l+3}. \tag{47}\]  
For example, the values of \(C_{2}(l)\) for specific values of \(l\) are as follows: \(C_{2}(10)\approx 1.46\), \(C_{2}(15)\approx 1.48\), and \(C_{2}(20)\approx 1.49\). Furthermore, as \(l\) increases, the reduction factor \(C_{2}(l)\) (see (47)) continues to grow, asymptotically approaching the value \(1.50\). It is important to note that the same reduction factor of computational complexity is also achieved when implementing the exponentiation procedure (44).