Residue number system

Residue number system

A residue number system (RNS) represents a large integer using a set of smaller integers, so that computation may be performed more efficiently. It relies on the Chinese remainder theorem of modular arithmetic for its operation, a mathematical idea from Sun Tsu Suan-Ching (Master Sun’s Arithmetic Manual) in the 4th century AD.

Defining a residue number system

A residue number system is defined by a set of "N" integer constants,

:{"m"1, "m"2, "m"3, ... , "m""N" },

referred to as the "moduli". Let "M" be the least common multiple of all the "m""i".

Any arbitrary integer "X" smaller than "M" can be represented in the defined residue number system as a set of "N" smaller integers

:{"x"1, "x"2, "x"3, ... , "x""N"}

with

:"x""i" = "X" "modulo" "m""i"

representing the residue class of "X" to that modulus.

Note that for maximum representational efficiency it is imperative that all the moduli are coprime; that is, no modulus may have a common factor with any other. "M" is then the product of all the "m"i.

Operations on RNS numbers

Once represented in RNS, many arithmetic operations can be efficiently performed on the encoded integer. For the following operations, consider two integers, "A" and "B", represented by "a""i" and "b""i" in an RNS system defined by "m""i" (for "i" from 0 ≤ "i" ≤ "N").

Addition and subtraction

Addition (or subtraction) can be accomplished by simply adding (or subtracting) the small integer values, modulo their specific moduli. That is,:C=Apm B mod Mcan be calculated in RNS as:c_i=a_ipm b_i mod m_i

One has to check for overflow in these operations.

Multiplication

Multiplication can be accomplished in a manner similar to addition and subtraction. To calculate :C = A cdot B mod M, we can calculate::c_i = a_icdot b_i mod m_iAgain overflows are possible.

Division

Division in residue number systems is problematic. A paper describing one possible algorithm is available at [http://www.cs.rpi.edu/research/ps/93-9.ps] . On other hand, if "B" is coprime with "M" (that is b_i ot =0) then:C=Acdot B^{-1} mod Mcan be easily calculated by:c_i=a_i cdot b_i^{-1} mod m_iwhere B^{-1} is multiplicative inverse of "B" modulo "M", and b_i^{-1} is multiplicative inverse of b_i modulo m_i.

Practical 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. Because of this, it's particularly popular in hardware implementations.

Integer factorization

The RNS can improve efficiency of trial division. Let X=Ycdot Z a semiprime. Let m_1=2, m_2=3, m_3=5,dots represent first "N" primes. Assume that Y>m_N, Z>m_N. Then x_i=y_icdot z_i, where x_i ot = 0. The method of trial division is the method of exhaustion, and the RNS automatically eliminates all "Y" and "Z" such that y_i=0 or z_i=0, that is we only need to check:prod_{i=1}^N(m_i-1)=Mprod_{i=1}^Nleft(1-frac{1}{m_i} ight)numbers below "M". For example, "N" = 3, the RNS can automatically eliminate all numbers but

:1,7,11,13,17,19,23,29 mod 30

or 73% of numbers. For "N" = 25 when m_i are all prime numbers below 100, the RNS eliminates about 88% of numbers. One can see from the above formula the diminishing returns from the larger sets of moduli.

Associated mixed radix system

A number given by {x_1,x_2,x_3,ldots,x_n} in the RNS can be naturally represented in the "associated mixed radix system" (AMRS)

:X=sum_{i=1}^Nx^*_iM_{i-1}=x^*_1+m_1(x^*_2+m_2(cdots+m_{N-1}x^*_{N})cdots),where:M_0=1,M_i=prod_{j=1}^i m_i for i>0 and 0leq x^*_i

Note that after conversion from the RNS to AMRS, the comparison of numbers becomes straightforward.

ee also

* Covering system
* Reduced residue system


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Covering system — In mathematics, a covering system (also called a complete residue system) is a collection of finitely many residue classes whose union covers all the integers. Unsolved problems in mathematics For any arbitrarily large natural number N does there …   Wikipedia

  • Numeral system — This article is about different methods of expressing numbers with symbols. For classifying numbers in mathematics, see number system. For how numbers are expressed using words, see number names. Numeral systems by culture Hindu Arabic numerals… …   Wikipedia

  • List of number theory topics — This is a list of number theory topics, by Wikipedia page. See also List of recreational number theory topics Topics in cryptography Contents 1 Factors 2 Fractions 3 Modular arithmetic …   Wikipedia

  • Reduced residue system — A reduced residue system modulo n is a set of phi( n ) integers such that each integer is relatively prime to n and no two are congruent modulo n . Here phi denotes Euler s totient function.Facts*If { r 1, r 2, dots, r {varphi(n)} } is a reduced… …   Wikipedia

  • Number theory — A Lehmer sieve an analog computer once used for finding primes and solving simple diophantine equations. Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers (the… …   Wikipedia

  • P-adic number — In mathematics, the p adic number systems were first described by Kurt Hensel in 1897 [cite journal | last = Hensel | first = Kurt | title = Über eine neue Begründung der Theorie der algebraischen Zahlen | journal =… …   Wikipedia

  • p-adic number — In mathematics, and chiefly number theory, the p adic number system for any prime number p extends the ordinary arithmetic of the rational numbers in a way different from the extension of the rational number system to the real and complex number… …   Wikipedia

  • Quadratic residue — 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: Otherwise, q is called a quadratic nonresidue modulo n. Originally an abstract… …   Wikipedia

  • Winding number — The term winding number may also refer to the rotation number of an iterated map. This curve has winding number two around the point p. In mathematics, the winding number of a closed curve in the plane around a given point is an integer… …   Wikipedia

  • Class number formula — In number theory, the class number formula relates many important invariants of a number field to a special value of its Dedekind zeta function Contents 1 General statement of the class number formula 2 Galois extensions of the rationals 3 A …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”