This article has multiple issues. Please helpimprove it or discuss these issues on thetalk page.(Learn how and when to remove these messages) This articleis missing information about many aspects of the subject (see thetalk page). Please expand the article to include this information. Further details may exist on thetalk page.(July 2018) This articlerelies largely or entirely on asingle source. Relevant discussion may be found on thetalk page. Please helpimprove this article byintroducing citations to additional sources. Find sources: "Residue number system" – news ·newspapers ·books ·scholar ·JSTOR(July 2018) This article includes alist of references,related reading, orexternal links,but its sources remain unclear because it lacksinline citations. Please helpimprove this article byintroducing more precise citations.(July 2018) (Learn how and when to remove this message) (Learn how and when to remove this message)

Aresidue number system orresidue numeral system (RNS) is anumeral system representingintegers by their valuesmodulo severalpairwise coprime integers called the moduli. This representation is allowed by theChinese remainder theorem, which asserts that, ifM is the product of the moduli, there is, in an interval of lengthM, exactly one integer having any given set of modular values. Using a residue numeral system forarithmetic operations is also calledmulti-modular arithmetic.

Multi-modular arithmetic is widely used for computation with large integers, typically inlinear 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 includepolynomial greatest common divisor,Gröbner basis computation andcryptography.

A residue numeral system is defined by a set ofk integers

${\displaystyle \{m_1,m_2,m_3,\dots ,m_k\},}$

called themoduli, which are generally supposed to bepairwise coprime (that is, any two of them have agreatest common divisor equal to one). Residue number systems have been defined for non-coprime moduli, but are not commonly used because of worse properties.^[1]

An integerx is represented in the residue numeral system by thefamily of its remainders (indexed by the moduli of the indexes of the moduli)

${\displaystyle \{x_1,x_2,x_3,\dots ,x_k\}}$

underEuclidean division by the moduli. That is

${\displaystyle x_i=x\mathrm{mod}{m}_i,}$

and

for everyi

LetM be the product of all the${\displaystyle m_i}$. Two integers whose difference is a multiple ofM have the same representation in the residue numeral system defined by them_is. More precisely, theChinese remainder theorem asserts that each of theM different sets of possible residues represents exactly oneresidue class moduloM. That is, each set of residues represents exactly one integer${\displaystyle X}$ in the interval${\displaystyle 0,\dots ,M-1}$. For signed numbers, the dynamic range is$-\lfloor M/2\rfloor \le X\le \lfloor (M-1)/2\rfloor$(when${\displaystyle M}$ is even, generally an extra negative value is represented).^[2]

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

${\displaystyle [m_1,\dots ,m_k]}$

is the list of moduli, the sum of the integersx andy, respectively represented by the residues${\displaystyle [x_1,\dots ,x_k]}$ and${\displaystyle [y_1,\dots ,y_k],}$ is the integerz represented by${\displaystyle [z_1,\dots ,z_k],}$ such that

${\displaystyle z_i=(x_i+y_i)\mathrm{mod}{m}_i,}$

fori = 1, ...,k (as usual, mod denotes themodulo operation consisting of taking the remainder of theEuclidean 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 avoidingoverflow 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.^[3]

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 ofM. 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 asEuclidean division andEuclidean algorithm.

Division in residue numeral systems is problematic. On the other hand, if${\displaystyle B}$ is coprime with${\displaystyle M}$ (that is${\displaystyle b_i\ne 0}$) then

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

can be easily calculated by

${\displaystyle c_i=a_i\cdot b_i^{-1}\mathrm{mod}{m}_i,}$

where${\displaystyle B^{-1}}$ ismultiplicative inverse of${\displaystyle B}$ modulo${\displaystyle M}$, and${\displaystyle b_i^{-1}}$ is multiplicative inverse of${\displaystyle b_i}$ modulo${\displaystyle m_i}$.

This sectionneeds expansion. You can help byadding to it.(July 2018)

RNS have applications in the field ofdigitalcomputer 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.

• Covering system
• Reduced residue system

• Szabo, Nicholas S.; Tanaka, Richard I. (1967).Residue Arithmetic and its Applications to Computer Technology (1 ed.). New York, USA:McGraw-Hill.
• Sonderstrand, Michael A.; Jenkins, W. Kenneth; Jullien, Graham A.; Taylor, Fred J., eds. (1986).Residue Number System Arithmetic: Modern Applications in Digital Signal Processing. IEEE Press Reprint Series (1 ed.). New York, USA:IEEE Circuits and Systems Society,IEEE Press.ISBN 0-87942-205-X.LCCN 86-10516. IEEE order code PC01982. (viii+418+6 pages)
• Chervyakov, N. I.; Molahosseini, A. S.; Lyakhov, P. A. (2017).Residue-to-binary conversion for general moduli sets based on approximate Chinese remainder theorem.International Journal of Computer Mathematics, 94:9, 1833-1849, doi: 10.1080/00207160.2016.1247439.
• Fin'ko [Финько], Oleg Anatolevich [Олег Анатольевич] (June 2004)."Large Systems of Boolean Functions: Realization by Modular Arithmetic Methods".Automation and Remote Control.65 (6):871–892.doi:10.1023/B:AURC.0000030901.74901.44.ISSN 0005-1179.LCCN 56038628.S2CID 123623780.CODEN AURCAT.Mi at1588.
• Chervyakov, N. I.; Lyakhov, P. A.; Deryabin, M. A. (2020).Residue Number System-Based Solution for Reducing the Hardware Cost of a Convolutional Neural Network.Neurocomputing, 407, 439-453, doi: 10.1016/j.neucom.2020.04.018.
• Bajard, Jean-Claude; Méloni, Nicolas; Plantard, Thomas (2006-10-06) [July 2005]."Efficient RNS bases for Cryptography"(PDF).IMACS'05: World Congress: Scientific Computation Applied Mathematics and Simulation. Paris, France. HAL Id: lirmm-00106470.Archived(PDF) from the original on 2021-01-23. Retrieved2021-01-23. (1+7 pages)
• Omondi, Amos; Premkumar, Benjamin (2007).Residue Number Systems: Theory and Implementation. London, UK:Imperial College Press.ISBN 978-1-86094-866-4. (296 pages)
• Mohan, P. V. Ananda (2016).Residue Number Systems: Theory and Applications (1 ed.).Birkhäuser /Springer International Publishing Switzerland.doi:10.1007/978-3-319-41385-3.ISBN 978-3-319-41383-9.LCCN 2016947081. (351 pages)
• Amir Sabbagh, Molahosseini; de Sousa, Leonel Seabra; Chip-Hong Chang, eds. (2017-03-21).Embedded Systems Design with Special Arithmetic and Number Systems (1 ed.).Springer International Publishing AG.doi:10.1007/978-3-319-49742-6.ISBN 978-3-319-49741-9.LCCN 2017934074. (389 pages)
• "Division algorithms". Archived fromthe original on 2005-02-17. Retrieved2023-08-24.
• Knuth, Donald Ervin.The Art of Computer Programming.Addison Wesley.
• Harvey, David (2010)."A multimodular algorithm for computing Bernoulli numbers".Mathematics of Computation.79 (272):2361–2370.arXiv:0807.1347.doi:10.1090/S0025-5718-2010-02367-1.S2CID 11329343.
• Lecerf, Grégoire; Schost, Éric (2003). "Fast multivariate power series multiplication in characteristic zero".SADIO Electronic Journal on Informatics and Operations Research.5 (1):1–10.
• Orange, Sébastien; Renault, Guénaël; Yokoyama, Kazuhiro (2012)."Efficient arithmetic in successive algebraic extension fields using symmetries".Mathematics in Computer Science.6 (3):217–233.doi:10.1007/s11786-012-0112-y.S2CID 14360845.
• Yokoyama, Kazuhiro (September 2012). "Usage of modular techniques for efficient computation of ideal operations".International Workshop on Computer Algebra in Scientific Computing. Berlin / Heidelberg, Germany: Springer. pp. 361–362.
• Hladík, Jakub; Šimeček, Ivan (January 2012). "Modular Arithmetic for Solving Linear Equations on the GPU".Seminar on Numerical Analysis. pp. 68–70.
• Pernet, Clément (June 2015). "Exact linear algebra algorithmic: Theory and practice".Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation.Association for Computing Machinery. pp. 17–18.
• Lecerf, Grégoire (2018). "On the complexity of the Lickteig–Roy subresultant algorithm".Journal of Symbolic Computation.
• Yokoyama, Kazuhiro; Noro, Masayuki; Takeshima, Taku (1994)."Multi-Modular Approach to Polynomial-Time Factorization of Bivariate Integral Polynomials".Journal of Symbolic Computation.17 (6):545–563.doi:10.1006/jsco.1994.1034.
• Isupov, Konstantin (2021). "High-Performance Computation in Residue Number System Using Floating-Point Arithmetic".Computation.9 (2): 9.doi:10.3390/computation9020009. ISSN 2079-3197.

• Modular arithmetic
• Computer arithmetic

• Articles with short description
• Short description is different from Wikidata
• Articles to be expanded from July 2018
• Articles needing additional references from July 2018
• All articles needing additional references
• Articles lacking in-text citations from July 2018
• All articles lacking in-text citations
• Use dmy dates from January 2021
• Articles with multiple maintenance issues
• All articles to be expanded