Residue number system
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)(Learn how and when to remove this template message)
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
for every i
Let M be the product of all the . Two integers whose difference is a multiple of M have the same representation in the residue numeral system defined by the uis. More precisely, the Chinese remainder theorem asserts that each of the M different sets of possible residues represents exactly one residue class modulo M. That is, each set of residues represents exactly one integer in the interval 0, ..., M.
In applications where one is also interested with negative integers, it is often more convenient to represent integers belonging to an interval centered at 0. In this case, if M is odd, each set of residues represents exactly one integer of absolute value at most M.
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
is the list of moduli, the sum of the integers x and y, respectively represented by the residues and is the integer z represented by such that
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.
If two integers are equal, then all their residues are equal. Conversely, if all residues are equal, then the two integers are equal, or their differences is a multiple of M. It follows that testing equality is easy.
At the opposite, testing inequalities (x < y) 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 Euclidean division and Euclidean algorithm.
Division in residue numeral systems is problematic. A paper describing one possible algorithm is available at . On the other hand, if is coprime with (that is ) then
can be easily calculated by
where is multiplicative inverse of modulo , and is multiplicative inverse of modulo .
This section needs expansion. You can help by adding to it. (July 2018)
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.
- Behrooz Parhami, Computer Arithmetic: Algorithms and Hardware Design. 2nd edition, Oxford University Press, New York, 2010. 641+xxv p. ISBN 978-0-19-532848-6.
- Jean-Claude Bajard, Nicolas Meloni and Thomas Plantard, Efficient RNS bases for Cryptography, IMACS'05: World Congress: Scientific Computation Applied Mathematics and Simulation. 2005.
- O. A. Fin'ko, Large Systems of Boolean Functions: Realization by Modular Arithmetic Methods, Automation and Remote Control, 65 (2004), no. 6, 871–892.
- Amos Omondi, Benjamin Premkumar. Residue Number Systems: Theory and Implementation. Imperial College Press. London. 2007. 296 p. ISBN 978-1-86094-866-4.
- Ananda Mohan, P.V. Residue Number Systems, Springer International Publishing. 2016. 351 p. ISBN 978-3-319-41385-3.
- Amir Sabbagh, Molahosseini, Leonel Seabra de Sousa, and Chip-Hong Chang (editors), Embedded Systems Design with Special Arithmetic and Number Systems, Springer International Publishing. 21 March 2017. 389 p. ISBN 978-3-319-49742-6.