## 3 Use of Special Type Moduli  
To improve the performance of RNS, many researchers are considering moduli of a special kind \(\left\{2^{n}-1,2^{n},2^{n}+1\right\}\)[8], \(\left\{2^{2n},2^{2n-1}-1,2^{2n}-1,2^{2n+1}-1\right\}\)[9], \(\left\{2^{k}-3,2^{k}-2,2^{k}-1\right\}\) and \(\left\{2^{k}+1,2^{k}+2,2^{k}+3\right\}\)[10], \(\left\{2^{2n-5}-1,\ 2^{2n-3}-1,\ 2^{2n-2}+1,\ 2^{2n-1}-1,\right.\) \(2^{2n-1}+1,2^{2n}\), \(2^{2n}+1\)[12], \(\left\{2^{2n},2^{n}+1,2^{n}-1,2^{n}+3,2^{n}-3\right\}\)[13]. The most interesting among the reverse conversion methods is the optimization for the moduli set \(\left\{2^{n}-1,2^{n},2^{n}+1\right\}\), which was proposed in the article [8]. The most efficient implementations are based on the modulo \(2^{n}-1\) for which a number of properties are satisfied:  
* The sign change (additive inversion) is achieved by bitwise negation, i.e., \(\left|-z\right|_{2^{n}-1}=\left|z\right|_{2^{n}-1}=\left|\left(z_{n-1}\ldots z _{0}\right)\right|_{2^{n}-1}\), e.g., \(\left|-5\right|_{7}=\left|-101_{2}\right|_{7}=\left|\overline{101_{2}}\right| _{7}=\left|\left(010_{2}\right)\right|_{7}=2\). * The multiplication by \(2^{d}\) can be performed by a cyclic shift to the left by \(d\) digits, i.e., \(\left|2^{d}z\right|_{2^{n}-1}=\left|z_{n-d-1}\ldots z_{0}z_{n-1}\ldots z_{n-d} \right|_{2^{n}-1}\), e.g., \(\left|2\cdot 5\right|_{7}=\left|2\cdot 101_{2}\right|_{7}=3\). * Multiplication by multiplicative inversion \(\left|2^{-d}\right|_{2^{n}-1}\) can be performed by a cyclic shift to the right by \(d\) positions or to the left by \(n-d\) positions, since \(\left|2^{-d}z\right|_{2^{n}-1}=\left|2^{n-d}z\right|_{2^{n}-1}\), i.e., \(\left|2^{-d}z\right|_{2^{n}-1}=\left|z_{d-1}\ldots z_{0}z_{n-1}\ldots z_{d} \right|_{2^{n}-1}\), e.g., \(\left|2^{-1}\cdot 5\right|_{7}=\left|2^{-1}\cdot 101_{2}\right|_{7}=110_{2}\right|_{7}=3\). * For any non-negative integer \(i\), \(\left|2^{i\cdot n}\right|_{2^{n}-1}=1\), then the \((sn)-\)bit number can be represented as \[\left|\sum_{i=0}^{s-1}2^{nit}\Big{(}y_{n(i+1)-1}\ldots y_{ni}\Big{)}\right|_{2^{ n}-1}=\left|\sum_{i=0}^{s-1}\Big{(}y_{n(i+1)-1}\ldots y_{ni}\Big{)}\right|_{2^{ n}-1}\]  
The article [8] is based on the idea that an expression for the reverse conversion based on the CRT (1) can be represented in a form, where the constant and the variables can be separated:  
\[X=\left|\left(\sum_{i=1}^{n}b_{i}\cdot x_{i}\right)+C_{k}\right|_{p}\]First, one takes from the set \(\{2^{n},2^{n}-1,2^{n}+1\}\) two moduli \(\{p_{2},p_{3}\}=\{2^{n}-1,2^{n}+1\}\) for which the number \(X_{23}=\{x_{2},x_{3}\}\) is found from CRT:  
\[X_{23}= \left|p_{3}\cdot x_{2}\cdot\left|p_{3}^{-1}\right|_{p_{2}}+p_{2} \cdot x_{3}\cdot\left|p_{2}^{-1}\right|_{p_{3}}\right|_{p_{2}p_{3}}=\] \[=\left|(2^{n}+1)\cdot 2^{n-1}\cdot x_{2}+(2^{n}-1)\cdot 2^{n-1} \cdot x_{3}\right|_{2^{2n}-1}=\] \[=\left|2^{n-1}\cdot((2^{n}+1)\cdot x_{2}+(2^{n}-1)x_{3})\right|_ {2^{2n}-1}\]  
Based on the MRC for the set of moduli \(\{p_{1},p_{2}p_{3}\}\), the number \(X=\{x_{1},X_{23}\}\) is found:  
\[X=x_{1}+p_{1}\left|(X_{23}-x_{1})\frac{1}{p_{1}}\right|_{p_{2}p_{3}}=x_{1}+2^ {n}X_{h}, \tag{12}\]  
where  
\[X_{h}= \left|(X_{23}-x_{1})2^{-1}\right|_{2^{2n}-1}=\] \[=\left|\left(2^{n-1}((2^{n}+1)x_{2}+(2^{n}-1)x_{3})-x_{1}\right) 2^{-1}\right|_{2^{2n}-1}= \tag{13}\] \[=\left|-x_{1}2^{-n}+x_{2}(2^{n}+1)2^{-1}+x_{3}(2^{n}-1)2^{-1} \right|_{2^{2n}-1}\]  
The optimization of the expression (13) is possible by bitwise operations. The first term can be represented as follows:  
\[\left|-x_{1}\cdot 2^{-n}\right|_{2^{2n}-1}=\left|2^{-1}\left((\bar{x}_{1,n-2} \ldots\bar{x}_{1,0})||\underbrace{(0\ldots 0)}_{n}||\bar{x}_{1,n-1}\right)+(2^{-n}-1) \right|_{2^{2n}-1}.\]  
The second term appears as:  
\[X=\left|\left(\sum_{i=1}^{n}b_{i}\cdot x_{i}\right)+C_{k}\right|_{p}\]0  
The third term can be represented as:  
\[X=\left|\left(\sum_{i=1}^{n}b_{i}\cdot x_{i}\right)+C_{k}\right|_{p}\]1 \[=\left|2^{-1}\left(