Residue number system

src: i.ytimg.com

A residue numeral 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 Sunzi Suanjing (Master Sun's Arithmetic Manual) in the 4th century AD.

Video Residue number system

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.

Maps Residue number system

Defining a residue numeral system

A residue numeral 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 numeral 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.

For representational efficiency the moduli should be pairwise coprime; that is, no modulus should 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, and a product of 8, resulting in the same representation for different values smaller than the product.

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

src: iiif.elifesciences.org

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,

${\displaystyle C=A\pm B\mod M}$

can be calculated in RNS as

${\displaystyle c_{i}=a_{i}\pm b_{i}\mod m_{i}}$

One does not have to check for overflow in these operations.

Multiplication

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

${\displaystyle C=A\cdot B\mod M,}$

we can calculate:

${\displaystyle c_{i}=a_{i}\cdot b_{i}\mod m_{i}}$

Again overflows are not possible.

Division

Division in residue numeral 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 ${\displaystyle b_{i}\not =0}$) then

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

can be easily calculated by

${\displaystyle c_{i}=a_{i}\cdot b_{i}^{-1}\mod m_{i}}$

where ${\displaystyle B^{-1}}$ is multiplicative inverse of B modulo M, and ${\displaystyle b_{i}^{-1}}$ is multiplicative inverse of ${\displaystyle b_{i}}$ modulo ${\displaystyle m_{i}}$.

src: pharmrev.aspetjournals.org

Integer factorization

The RNS can improve efficiency of trial division, essentially a form of wheel sieving. The RNS using n primes represents a number coprime to their product if and only if it has no 0s. For example, using the primes 2, 3, and 5, the RNS can automatically eliminate all numbers but

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

or 73% of numbers. Using the 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.

src: iiif.elifesciences.org

Associated mixed radix system

A numeral given by ${\displaystyle \{x_{1},x_{2},x_{3},\ldots ,x_{n}\}}$ in the RNS can be naturally represented in the associated mixed radix system (AMRS)

${\displaystyle 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

${\displaystyle M_{0}=1,M_{i}=\prod _{j=1}^{i}m_{j}}$ for ${\displaystyle i>0}$ and ${\displaystyle 0\leq x_{i}<m_{i}.}$

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

src: media.springernature.com

See also

• Covering system
• Reduced residue system

src: iiif.elifesciences.org

References

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

Source of the article : Wikipedia