Tobin's q

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₁, m₂, m₃, ... , 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₁, x₂, x₃, ... , 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.

For example RNS(4|2) has non-coprime moduli, resulting in the same representation for different values.

 (3)decimal = (3|1)RNS(4|2)
 (7)decimal = (3|1)RNS(4|2)

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=A\pm BmodM$

can be calculated in RNS as

$c_i=a_i\pm 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 BmodM,$

we can calculate:

$c_i=a_i\cdot b_{i}mod{m}_i$

Again overflows are possible.

Division

Division in residue number systems is problematic. A paper describing one possible algorithm is available at [1]. On the other hand, if B is coprime with M (that is $b_i≠0$) then

$C=A\cdot B^{-1}modM$

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$.

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.

Integer factorization

The RNS can improve efficiency of trial division. Let $X=Y\cdot 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_i\cdot z_i$, where $x_i≠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)=M\prod _{i=1}^N(1-\frac{1}{m_i})$

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,\dots ,x_n\}$ in the RNS can be naturally represented in the associated mixed radix system (AMRS)

$X=\sum _{i=1}^N{x}_i{M}_{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}_j$ for $i>0$ and $0\le x_i<m_i.$

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

See also

• Covering system
• Reduced residue system

References

• Efficient RNS bases for Cryptography // IMACS'05: World Congress: Scientific ComputationApplied Mathematics and Simulation. 2005.