RNS stands for Residue Number System, and is a generalized method for representing numbers and performing fast calculations. RNS can be used to convert operations such as multiplication and addition of large numbers into multiplication and addition of smaller numbers, thus allowing the original operations to be performed in parallel.
Computation
Convert to RNS
Converting a number $X$ to an RNS representation is relatively simple. First, a set of mutually qualitative numbers is chosen as the base of the RNS representation, and then $X$ is modeled according to each number in the base, and the resulting set of numbers is the representation of X under the RNS.
$$ x_i = X \mod m_i $$
Arithmetic operations on RNS
Modulo multiplication, modulo addition and modulo subtraction operations can be performed on RNS domains. Division cannot be computed under the RNS representation in the same simple way, but has been studied to some extent. Multiplication, addition and subtraction are all implemented in a similar way, by directly performing the operations modulo $m_i$ on each of the numbers in the representation.
$$ z_i = x_i \odot y_i \mod m_i,~\textrm{where $\odot$ can be } +, -, \times. $$
This is largely enabled by the Chinese Residual Theorem.
From RNS to Original Number
There are two main ideas for recovering the original numbers from the RNS representation, one is through the direct use of the Chinese Residual Theorem, and the other uses a mixed-radix representation (MRS), where the RNS is converted to the MRS and then computed to get the final result.
Chinese Remainder Theorem (CRT)
\[ \begin{aligned} X = \sum_{i = 1}^k M_{i,1}\xi_i \mod M_1, \\ \xi_i = \left\vert\frac{x_i}{M_{i,1}}\right\vert_{m_i} = x_i \left\vert{M_{i,1}^{-1}}\right\vert \mod m_i, \\ M_{i,1} = \frac{M_1}{m_i}. \end{aligned} \]
However, since $M_i$ is usually large, $\mod M_i$ is still difficult to compute. Therefore, in this design, $\mod M_i$ is usually realized by subtracting multiple times $M_i$.
\[ X = \sum_{i=1}^k M_{i,1}\xi_i \mod M_1 = \sum_{i=1}^k M_{i,1}\xi_i - \alpha M_1, \textrm{with} \alpha < k. \]
There are two ways to calculate the $\alpha$ in it.
- The method proposed by Shenoy et. Kumaresan introduces an additional modulus $m_\text{extra}$, $\alpha$ which can be estimated by
\[ \begin{aligned} x_{\text{extra}} &= \left\vert {\sum_{i=1}^k {M_{i,1}} \xi_i - \alpha M_1} \right\vert_{m_\text{extra}} \Leftrightarrow \\ \left\vert {\alpha} \right\vert_{m_{\text{extra}}} &= \left\vert {\left\vert {\sum_{i=1}^{k}M_{i,1}\xi_i - x_{\text{extra}}}\right\vert_{m_\text{extra}}} {\left\vert {M_1^{-1}} \right\vert_{m_\text{extra}}} \right\vert_{m_\text{extra}}. \end{aligned} \]
- The method proposed by Kawamura et. al avoids the introduction of additional moduli and instead uses an immobile point approximation.
Mixed-Radix System
$$ X = \sum_{i=1}^{k} t_i \times (\prod_{j=1}^{i-1} m_j) $$
For each coordinate in MRS, the calculation is as follows:
\[ \begin{aligned} t_1 &= x_1 \\ t_2 &= \left\vert m_1^{-1} \right\vert_{m_2} \times (x_2 - t_1) \mod m_2 \\ t_3 &= \left\vert (m_1m_2)^{-1} \right\vert_{m_3} \times (x_3 - (t_2m_1 + t_1)) \mod m_3 \\ \vdots \\ t_i &= \left\vert (\prod_{j=1}^{i-1}m_j)^{-1} \right\vert_{m_i} \times (x_i - (\sum_{j=1}^{i-1}(t_j \prod_{l=1}^{j-1}m_l))) \mod m_i \\ \end{aligned} \]
Select the Moduli
Since the moduli needs to be mutually prime integers, there are several strategies for selecting them.
- use consecutive primes
- use powers of small primes, combined with consecutive primes
- use only $2^n$ or $2^n - 1$ (Low-cost Moduli) for ease of modulo operation
- use $2^n + 1$, $2^n$, $2^n - 1$ for easy modulo operations
In addition to this, it is necessary to ensure that $\prod m_i $ is large enough in order to be able to represent all numbers in domain.
References: