Dr. P. V. Ananda Mohan has received Ph.D degree in electrical communication engineering from Indian Institute of Science, Bangalore, in 1975. From 1973 till December 2003, he was with I.T.I. Limited R&D Division. Later, till 2014, he was with Electronics Corporation of India Limited, Bangalore. He is at present with Centre for Advanced Computing (CDAC), Bangalore as Technology Advisor.
Digital computation and Digital signal processing need arithmetic processors of moderate word lengths 16 to 32 bits.Fixed point and floating point arithmetic units which can perform addition, subtraction, multiplication are extensively employed. On the other hand, several cryptographic algorithms used for authentication such as RSA (Rivest,Shamir and Adleman) cryptosystems  need to perform operations on large word length operands of lengths ranging from 1024 bits to 4096 bits. Other authentication systems use Elliptic Curve Cryptography  where word lengths range from 160 bits to 256 bits. These can be realized in embedded systems using resident processors such ARM or using DSPs using word based implementations. In some applications such as Homomorphic encryption  used for computing on encrypted data in cloud computing, processors need to handle words of the size 768, 000 bits. Residue Number Systems facilitate handling such big number operations using smaller word length processors.
We will consider these in the next few sections in some detail. We will present several example to facilitate easy understanding and avoid too much of theory.
Let us consider a conventional 32 bit processor for illustration. It needs to perform several 32 bit operations.Consider simple addition of two binary numbers. The time needed using carry
propagate adders or Ripple carry adders is 31 full-adder delays. Most text books ,  give improved designs using carry-look-ahead techniques involving two or more levels so as to reduce the delay for computing the carrybit. Today the benchmark is roughly log2n full adder delay for a n-bit two operand addition. Thus for a given technology (i.e. specified gate delay), this is the minimum time needed. This can be reduced only if we use smaller width operands. Thus, one solution is to represent the 32 bit word using smaller numbers and then being able to perform operations faster. Earlier logarithmic systems have been tried which can convert the time consuming multiplication or division operations to addition and subtraction. But we need log tables to convert from normal form to logarithms and after multiplication or division conversion back to normal form. Unfortunately, addition and subtractions cannot be done easily in logarithmic number system.
The concept of RNS is attributed to Chinese who have discovered the so called Chinese Remainder Theorem.
The problem given by Sun Tzu in 3rd Century is as follows:
- We have things of which we do not know the number
- If we count them by threes, wehave two left over
- If we count them by fives, we have three left over
- If we count them by sevens, we have two left over