Residue number system

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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[edit]

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[edit]

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 and subtraction[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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

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

See also[edit]

References[edit]

  1. ^ Parhami, Computer Arithmetic, Algorithms and Hardware Design