# Residue number system

A residue number system (RNS) represents a large integer using a set of smaller integers, so that computation may be performed more efficiently. It relies on the Chinese remainder theorem of modular arithmetic for its operation, a mathematical idea from Sun Tsu Suan-Ching (Master Sun’s Arithmetic Manual) in the 4th century AD.

## Practical applications

RNS have applications in the field of digital computer arithmetic. By decomposing in this a large integer into a set of smaller integers, a large calculation can be performed as a series of smaller calculations that can be performed independently and in parallel.

## Defining a residue number system

A residue number system is defined by a set of N integer constants,

{m1, m2, m3, ... , mN },

referred to as the moduli. Let M be the least common multiple of all the mi.

Any arbitrary integer X smaller than M can be represented in the defined residue number system as a set of N smaller integers

{x1, x2, x3, ... , xN}

with

xi = X modulo mi

representing the residue class of X to that modulus.

Note that for maximum representational efficiency it is imperative that all the moduli be coprime; that is, no modulus may have a common factor with any other. M is then the product of all the mi.

For example RNS(4|2) has non-coprime moduli, resulting in the same representation for different values.[1]

 (3)decimal = (3|1)RNS(4|2)
(7)decimal = (3|1)RNS(4|2)


## Operations on RNS numbers

Once represented in RNS, many arithmetic operations can be efficiently performed on the encoded integer. For the following operations, consider two integers, A and B, represented by ai and bi in an RNS system defined by mi (for i from 0 ≤ iN).

Addition (or subtraction) can be accomplished by simply adding (or subtracting) the small integer values, modulo their specific moduli. That is,

$C=A\pm B \mod M$

can be calculated in RNS as

$c_i=a_i\pm b_i \mod m_i$

One has to check for overflow in these operations.

### Multiplication

Multiplication can be accomplished in a manner similar to addition and subtraction. To calculate

$C = A \cdot B \mod M,$

we can calculate:

$c_i = a_i\cdot b_i \mod m_i$

Again overflows are possible.

### Division

Division in residue number systems is problematic. A paper describing one possible algorithm is available at [1]. On the other hand, if B is coprime with M (that is $b_i\not =0$) then

$C=A\cdot B^{-1} \mod M$

can be easily calculated by

$c_i=a_i \cdot b_i^{-1} \mod m_i$

where $B^{-1}$ is multiplicative inverse of B modulo M, and $b_i^{-1}$ is multiplicative inverse of $b_i$ modulo $m_i$.

## Integer factorization

The RNS can improve efficiency of trial division. Let $X=Y\cdot Z$ a semiprime. Let $m_1=2, m_2=3, m_3=5,\dots$ represent first N primes. Assume that $Y>m_N$, $Z>m_N$. Then $x_i=y_i\cdot z_i$, where $x_i\not = 0$. The method of trial division is the method of exhaustion, and the RNS automatically eliminates all Y and Z such that $y_i=0$ or $z_i=0$, that is we only need to check

$\prod_{i=1}^N(m_i-1)=M\prod_{i=1}^N\left(1-\frac{1}{m_i}\right)$

numbers below M. For example, N = 3, the RNS can automatically eliminate all numbers but

1,7,11,13,17,19,23,29 mod 30

or 73% of numbers. For N = 25 when $m_i$ are all prime numbers below 100, the RNS eliminates about 88% of numbers. One can see from the above formula the diminishing returns from the larger sets of moduli.

A number given by $\{x_1,x_2,x_3,\ldots,x_n\}$ in the RNS can be naturally represented in the associated mixed radix system (AMRS)

$X=\sum_{i=1}^Nx_iM_{i-1}=x_1+m_1(x_2+m_2(\cdots+m_{N-1}x_{N})\cdots),$

where

$M_0=1,M_i=\prod_{j=1}^i m_j$ for $i>0$ and $0\leq x_i

Note that after conversion from the RNS to AMRS, the comparison of numbers becomes straightforward.