Residue number system

From Wikipedia, the free encyclopedia

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.

1 Defining a residue number system
2 Operations on RNS numbers
3 Practical applications
4 Integer factorization
5 Associated mixed radix system
6 See also

[edit] 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 are coprime; that is, no modulus may have a common factor with any other. M is then the product of all the m_i.

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

[edit] 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 to check for overflow in these operations.

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

[edit] Division

Division in residue number systems is problematic. A paper describing one possible algorithm is available at [1]. On 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$ .

[edit] 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. Because of this, it's particularly popular in hardware implementations.

[edit] 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,...$ 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.