Residue number system

Last updated July 09, 2024

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 $M$ is the product of the moduli, there is, in an interval of length $M$ , 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.

Definition

A residue numeral system is defined by a set of $k$ integers

\{m_{1},m_{2},m_{3},\ldots ,m_{k}\},

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. Therefore, they will not be considered in the remainder of this article.^[1]

An integer $x$ is represented in the residue numeral system by the set of its remainders

\{x_{1},x_{2},x_{3},\ldots ,x_{k}\}

under Euclidean division by the moduli. That is

x_{i}=x\operatorname {mod} m_{i},

and

0\leq x_{i}<m_{i}

for every $i$

Let $M$ be the product of all the $m_{i}$ . Two integers whose difference is a multiple of $M$ have the same representation in the residue numeral system defined by the $m i$ s. 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 $X$ in the interval $0,\dots ,M-1$ . For signed numbers, the dynamic range is ${\textstyle {-\lfloor M/2\rfloor }\leq X\leq \lfloor (M-1)/2\rfloor }$ (when $M$ is even, generally an extra negative value is represented).^[2]

Arithmetic operations

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

[m_{1},\ldots ,m_{k}]

is the list of moduli, the sum of the integers $x$ and $y$ , respectively represented by the residues $[x_{1},\ldots ,x_{k}]$ and $[y_{1},\ldots ,y_{k}],$ is the integer $z$ represented by $[z_{1},\ldots ,z_{k}],$ such that

z_{i}=(x_{i}+y_{i})\operatorname {mod} m_{i},

for $i = 1, ..., k$ (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.^[3]

Comparison

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 as Euclidean division and Euclidean algorithm.

Division

Division in residue numeral systems is problematic. On the other hand, if $B$ is coprime with $M$ (that is $b_{i}\not =0$ ) then

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

can be easily calculated by

c_{i}=a_{i}\cdot b_{i}^{-1}\mod m_{i},

where $B^{-1}$ is multiplicative inverse of $B$ modulo $M$ , and $b_{i}^{-1}$ is multiplicative inverse of $b_{i}$ modulo $m_{i}$ .

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.

Related Research Articles

In number theory, two integers $a$ and $b$ are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides $a$ does not divide $b$ , and vice versa. This is equivalent to their greatest common divisor (GCD) being 1. One says also $a$ is prime to $b$ or $a$ is coprime with $b$ .

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

<span class="mw-page-title-main">Diophantine equation</span> Polynomial equation whose integer solutions are sought

In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, for which only integer solutions are of interest. A linear Diophantine equation equates to a constant the sum of two or more monomials, each of degree one. An exponential Diophantine equation is one in which unknowns can appear in exponents.

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements . It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as $or$

In number theory, given a prime number $p$ , the $p$ -adic numbers form an extension of the rational numbers which is distinct from the real numbers, though with some similar properties; $p$ -adic numbers can be written in a form similar to decimals, but with digits based on a prime number $p$ rather than ten, and extending to the left rather than to the right.

In number theory, Fermat's little theorem states that if $p$ is a prime number, then for any integer $a$ , the number $a p - a$ is an integer multiple of $p$ . In the notation of modular arithmetic, this is expressed as

The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in turn are important in cryptography.

In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that

In mathematics, for given real numbers a and b, the logarithm log_b a is a number x such that b^x = a. Analogously, in any group G, powers b^k can be defined for all integers k, and the discrete logarithm log_b a is an integer k such that b^k = a. In number theory, the more commonly used term is index: we can write x = ind_ra (mod m) (read "the index of a to the base r modulo m") for r^x ≡ a (mod m) if r is a primitive root of m and gcd(a,m) = 1.

In modular arithmetic, a number $g$ is a primitive root modulo $n$ if every number $a$ coprime to $n$ is congruent to a power of $g$ modulo $n$ . That is, $g$ is a primitive root modulo $n$ if for every integer $a$ coprime to $n$ , there is some integer $k$ for which $g$ ^$k$ ≡ $a$ . Such a value $k$ is called the index or discrete logarithm of $a$ to the base $g$ modulo $n$ . So $g$ is a primitive root modulo $n$ if and only if $g$ is a generator of the multiplicative group of integers modulo $n$ .

In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:

In modular arithmetic computation, Montgomery modular multiplication, more commonly referred to as Montgomery multiplication, is a method for performing fast modular multiplication. It was introduced in 1985 by the American mathematician Peter L. Montgomery.

In modular arithmetic, Thue's lemma roughly states that every modular integer may be represented by a "modular fraction" such that the numerator and the denominator have absolute values not greater than the square root of the modulus.

The Tonelli–Shanks algorithm is used in modular arithmetic to solve for r in a congruence of the form r² ≡ n, where p is a prime: that is, to find a square root of n modulo p.

In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same domain. Polynomial factorization is one of the fundamental components of computer algebra systems.

In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer $a$ is an integer $x$ such that the product $ax$ is congruent to 1 with respect to the modulus $m$ . In the standard notation of modular arithmetic this congruence is written as

In cryptography, Very Smooth Hash (VSH) is a provably secure cryptographic hash function invented in 2005 by Scott Contini, Arjen Lenstra and Ron Steinfeld. Provably secure means that finding collisions is as difficult as some known hard mathematical problem. Unlike other provably secure collision-resistant hashes, VSH is efficient and usable in practice. Asymptotically, it only requires a single multiplication per log(n) message-bits and uses RSA-type arithmetic. Therefore, VSH can be useful in embedded environments where code space is limited.

In number theory, a kth root of unity modulo n for positive integers k, n ≥ 2, is a root of unity in the ring of integers modulo n; that is, a solution x to the equation $. If k is the smallest such exponent for x, then x is called a primitive k th root of unity modulo n . See modular arithmetic for notation and terminology.$

References

↑ Parhami, Behrooz (2010). Computer Arithmetic: Algorithms and Hardware Designs (2 ed.). New York, USA: Oxford University Press. ISBN 978-0-19-532848-6. Archived from the original on 2020-08-04. Retrieved 2021-01-23. (xxv+641 pages)
↑ Hung, C.Y.; Parhami, B. (1994-02-01). "An approximate sign detection method for residue numbers and its application to RNS division" (PDF). Computers & Mathematics with Applications. 27 (4): 23–35. doi:10.1016/0898-1221(94)90052-3.
↑ Isupov, Konstantin (2020-04-07) [2020-03-20, 2020-03-08, 2020-02-17]. "Using Floating-Point Intervals for Non-Modular Computations in Residue Number System". IEEE Access . 8: 58603–58619. Bibcode:2020IEEEA...858603I. doi: 10.1109/ACCESS.2020.2982365 . ISSN 2169-3536.

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. Retrieved 2021-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 from the original on 2005-02-17. Retrieved 2023-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.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Parhami_2010-1] Parhami, Behrooz (2010). Computer Arithmetic: Algorithms and Hardware Designs (2 ed.). New York, USA: Oxford University Press. ISBN 978-0-19-532848-6. Archived from the original on 2020-08-04. Retrieved 2021-01-23. (xxv+641 pages)

[2] Hung, C.Y.; Parhami, B. (1994-02-01). "An approximate sign detection method for residue numbers and its application to RNS division" (PDF). Computers & Mathematics with Applications. 27 (4): 23–35. doi:10.1016/0898-1221(94)90052-3.

[Isupov_2020-3] Isupov, Konstantin (2020-04-07) [2020-03-20, 2020-03-08, 2020-02-17]. "Using Floating-Point Intervals for Non-Modular Computations in Residue Number System". IEEE Access . 8: 58603–58619. Bibcode:2020IEEEA...858603I. doi: 10.1109/ACCESS.2020.2982365 . ISSN 2169-3536.

[1]

[2]

[3]