Residue number system

A 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 N is the product of the moduli, there is, in an interval of length N, exactly one integer having any given set of modular values. The arithmetic of a residue numeral system is also called multi-modular arithmetic. A 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 N is the product of the moduli, there is, in an interval of length N, exactly one integer having any given set of modular values. The arithmetic of a residue numeral system 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. A residue numeral system is defined by a set of k integers 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). referred to as the moduli. Residue number systems have been defined for non-coprime moduli, but are not commonly used because of worse properties. Therefore, they will not be considered in the remainder of this article. An integer x is represented in the residue numeral system by the set of its remainders under Euclidean division by the moduli. That is