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,

{m₁, m₂, m₃, ... , m_N },

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

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

{x₁, x₂, x₃, ... , x_N}

with

x_i = X modulo m_i

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 m_i.

For example RNS(4|2) has non-coprime moduli, with an LCM of 4, not 8, resulting in the same representation for different values occurring between smaller numbers.

 (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 a_i and b_i in an RNS system defined by m_i (for i from 0 ≤ i ≤ N).

Addition and subtraction

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 not 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 not 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.

Associated mixed radix system

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}^{N}x_{i}M_{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}<m_{i}.$

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

See also

• Covering system
• Reduced residue system

References

• Efficient RNS bases for Cryptography // IMACS'05: World Congress: Scientific ComputationApplied Mathematics and Simulation. 2005.