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.

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.

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=Apm\; B\; mod\; M$can be calculated in RNS as:$c\_i=a\_ipm\; 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\_icdot\; 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 [http://www.cs.rpi.edu/research/ps/93-9.ps] . On other hand, if "B" is coprime with "M" (that is $b\_i\; ot\; =0$) then:$C=Acdot\; 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$.

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.

Integer factorization

The RNS can improve efficiency of trial division. Let $X=Ycdot\; 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\_icdot\; z\_i$, where $x\_i\; ot\; =\; 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)=Mprod\_\{i=1\}^Nleft(1-frac\{1\}\{m\_i\}\; ight)$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\}^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\_i$ for $i>0$ and

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

ee also

* Covering system
* Reduced residue system