Residue number system

Template:Short description Template:Multiple issues A residue number system or residue numeral system (RNS) is a numeral system representing integers by their values modulo several pairwise coprime integers called the moduli. This representation is allowed by the Chinese remainder theorem, which asserts that, if Template:Mvar is the product of the moduli, there is, in an interval of length Template:Mvar, exactly one integer having any given set of modular values. Using a residue numeral system for arithmetic operations is also called multi-modular arithmetic.

Multi-modular arithmetic is widely used for computation with large integers, typically in linear algebra, because it provides faster computation than with the usual numeral systems, even when the time for converting between numeral systems is taken into account. Other applications of multi-modular arithmetic include polynomial greatest common divisor, Gröbner basis computation and cryptography.

DefinitionEdit

A residue numeral system is defined by a set of Template:Mvar integers

<math>\{ m_1, m_2, m_3,\ldots, m_k\},</math>

called the moduli, which are generally supposed to be pairwise coprime (that is, any two of them have a greatest common divisor equal to one). Residue number systems have been defined for non-coprime moduli, but are not commonly used because of worse properties.<ref name="Parhami_2010"/>

An integer Template:Mvar is represented in the residue numeral system by the family of its remainders (indexed by the moduli of the indexes of the moduli)

<math>\{ x_1,x_2,x_3,\ldots,x_k \}</math>

under Euclidean division by the moduli. That is

<math> x_i = x \operatorname{mod}m_i,</math>

and

for every Template:Mvar

Let Template:Mvar be the product of all the <math>m_i</math>. Two integers whose difference is a multiple of Template:Mvar have the same representation in the residue numeral system defined by the Template:Maths. More precisely, the Chinese remainder theorem asserts that each of the Template:Mvar different sets of possible residues represents exactly one residue class modulo Template:Mvar. That is, each set of residues represents exactly one integer <math>X</math> in the interval <math>0,\dots,M-1</math>. For signed numbers, the dynamic range is <math display="inline">{-\lfloor M/2 \rfloor} \le X \le \lfloor (M-1)/2 \rfloor</math> (when <math>M</math> is even, generally an extra negative value is represented).<ref>Template:Cite journal</ref>

Arithmetic operationsEdit

For adding, subtracting and multiplying numbers represented in a residue number system, it suffices to perform the same modular operation on each pair of residues. More precisely, if

<math>[m_1, \ldots, m_k]</math>

is the list of moduli, the sum of the integers Template:Mvar and Template:Mvar, respectively represented by the residues <math>[x_1,\ldots, x_k]</math> and <math>[y_1,\ldots, y_k],</math> is the integer Template:Mvar represented by <math>[z_1,\ldots, z_k],</math> such that

<math>z_i= (x_i+y_i)\operatorname{mod} m_i,</math>

for Template:Math (as usual, mod denotes the modulo operation consisting of taking the remainder of the Euclidean division by the right operand). Subtraction and multiplication are defined similarly.

For a succession of operations, it is not necessary to apply the modulo operation at each step. It may be applied at the end of the computation, or, during the computation, for avoiding overflow of hardware operations.

However, operations such as magnitude comparison, sign computation, overflow detection, scaling, and division are difficult to perform in a residue number system.<ref name="Isupov_2020"/>

ComparisonEdit

If two integers are equal, then all their residues are equal. Conversely, if all residues are equal, then the two integers are equal or differ by a multiple of Template:Mvar. It follows that testing equality is easy.

At the opposite, testing inequalities (Template:Math) is difficult and, usually, requires to convert integers to the standard representation. As a consequence, this representation of numbers is not suitable for algorithms using inequality tests, such as Euclidean division and Euclidean algorithm.

DivisionEdit

Division in residue numeral systems is problematic. On the other hand, if <math>B</math> is coprime with <math>M</math> (that is <math>b_i\not =0</math>) then

can be easily calculated by

where <math>B^{-1}</math> is multiplicative inverse of <math>B</math> modulo <math>M</math>, and <math>b_i^{-1}</math> is multiplicative inverse of <math>b_i</math> modulo <math>m_i</math>.

ApplicationsEdit

Template:Expand section

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.

ReferencesEdit

Template:Reflist