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 generally credited to the Chinese philosopher Sun Tsu Suan-Ching in the 4th century AD.

Defining a residue number system

A residue number system is defined by a set of N + 1 integer constants,

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

referred to as the moduli. The moduli must all be coprime; so in particular no modulus may be a factor of any other. Let M be the product 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 + 1 smaller integers

{x₀, x₁, ... ''x_N}

with

x_i = X modulo m_i

representing the residue class of X to that modulus.

The integer X can then be recovered from the set of the x_i integers.

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 can be accomplished by simply adding the small integer values together, modulo their specific moduli. For example, a sum can be computed by calculating a set of sum_i values such that:

sum_i = ( a_i + b_i ) % m_i

Similarly, subtraction works the same way:

diff_i = (a_i – b_i ) % m_i

Multiplication

Multiplication can be accomplished in a manner similar to addition and subtraction. To calculate PROD = A * B, we can calculate:

prod_i = ( a_i * b_i ) % 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.