## 6 Discussion
### Computational Costs of Proposed MM Algorithm  
In RNS arithmetic, the implementation of MM (see (31)) reduces to performing modular operations on small bit-length residues concerning the moduli of the sets \(\mathbb{M}_{1}\) and \(\mathbb{M}_{2}\) using the lookup tables technique. To assess computational efficiency, we compare the computational costs presented in Table 1, where \(N_{\text{mo}}\) and \(N_{\text{mo}}^{*}\) represent the number of required modular operations at the corresponding steps of Algorithm 1 both in minimally redundant RNS and conventional non-redundant RNS, respectively. Additionally, \(C_{\text{mrs}}^{\prime\prime}\) and \(p_{\text{mrs}}\) denote the mixed-radix representations of the integers \(\mathbb{C}^{\prime\prime}\) and \(p\), respectively. Computing the modular code of the number \(C=AB\) requires \(k+1\) modular operations in a minimally redundant RNS, and \(k\) operations in a conventional RNS. \begin{table}
\begin{tabular}{l l l} \hline \hline
**Step** & \(\mathbf{N_{mo}}\) & \(\mathbf{N_{mo}^{*}}\) \\ \hline \(C=AB\) & \(k+1\) & \(k\) \\ \(X=\left|\mathbb{C}Y\right|_{M_{l}}\) & \(l+1\) & \(l\) \\ \(\rho_{l}(X)=\widehat{\rho}_{l}(X)+\delta_{l}(X)\) & \(l\) & \(\left(l^{2}+5l-10\right)/2\) \\ \(\operatorname{BEX}(X;\mathbb{M}_{1},\mathbb{M}_{2})\) & \(l(k-l)\) & \(l(k-l)\) \\ \(C^{\prime\prime}=\left(C+Xp\right)/M_{l}\) & \(k-l+1\) & \(k-l\) \\ \(\rho_{n}(C^{\prime\prime})=\widehat{\rho}_{n}(C^{\prime\prime})+\delta_{n}(C ^{\prime\prime})\) & \(k-l\) & \(\left((k-l)^{2}+5(k-l)-10\right)/2\) \\ \(\operatorname{BEX}(C^{\prime\prime};\mathbb{M}_{2},\mathbb{M}_{1})\) & \((k-l)l\) & \((k-l)l\) \\ \(C_{\text{mrs}}^{\prime\prime}=\operatorname{RC}(C^{\prime\prime})\) & \(\left(l^{2}+3l-8\right)/2\) & \(\left(l^{2}+3l-8\right)/2\) \\ \(Q=\operatorname{CMP}(C_{\text{mrs}}^{\prime\prime},p_{\text{mrs}})\) & \(l\) & \(l\) \\ \(\tilde{C}=C^{\prime\prime}-Qp\) & \(k+1\) & \(k\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The number of required modular operation. Computing the modular code of the number \(X=|CY|_{M_{l}}\) with respect to the moduli \(m_{1},m_{2},\ldots,m_{l}\) in the set \(\mathbb{M}_{1}\) requires \(l+1\) modular operations in a minimally redundant RNS, and \(l\) operations in a conventional RNS. The modular operation costs required to compute the rank \(\rho_{l}(X)\) of the number \(X\) with respect to the moduli in the set \(\mathbb{M}_{1}\) are based on the results presented in [27], and amount to \(l\) and \(\left(l^{2}+5l-10\right)/2\) modular operations, respectively (see Equations (14)-(18)). The base extension operation \(\mathrm{BEX}(X;\mathbb{M}_{1},\mathbb{M}_{2})\), which extends the modular code of the number \(X\) from the moduli set \(\mathbb{M}_{1}\) to \(\mathbb{M}_{2}\), requires \(l(k-l)\) modular operations in both minimally redundant and conventional RNS implementations (see Equation (19)). Computing the modular code of the number \(C^{\prime\prime}=\left(C+Xp\right)/M_{l}\) with respect to the moduli set \(\mathbb{M}_{2}\), while taking into account the redundant module \(m_{0}\), requires \(k-l+1\) modular operations in a minimally redundant RNS and \(k-l\) operations in a conventional RNS (see Equations (19)-(23)). Similarly, computing the rank \(\rho_{n}(C^{\prime\prime})\) of the number \(C^{\prime\prime}\) with respect to the moduli set \(\mathbb{M}_{2}\) requires \(k-l\) modular operations in a minimally redundant RNS, and \(((k-l)^{2}+5(k-l)-10)/2\) operations in a conventional RNS (see Equations (25)-(28) and [27]). The base extension operation \(\mathrm{BEX}(C^{\prime\prime};\mathbb{M}_{2},\mathbb{M}_{1})\), which maps the modular code of the number \(C^{\prime\prime}\) from \(\mathbb{M}_{2}\) back to \(\mathbb{M}_{1}\), also requires \((k-l)l\) modular operations in both minimally redundant and conventional RNS implementations (see Equation (29)). Calculating the mixed-radix representation \(C^{\prime\prime}_{mrs}\) of the number \(C^{\prime\prime}\) requires \((l^{2}+3l-8)/2\) modular operations, as shown in [28].