Home > cryptocurrencies > Residual Number System

Residual Number System


In this tutorial paper, we have introduced the concepts of Residue NumberSystems together with the description of procedures for performing various arithmetic operations. In current state of the art, RNS processors have been built for high Dynamic ranges up to 1024 bits using eight to ten moduli taking advantage of special powers of two related mutually prime numbers and massive mathematical operations as needed in some cryptographic pairing protocols [15] have been shown to be benefited by the use of Residue Number system. The parallelism possible with RNS based processors has been exploited to design cryptographic systems to prevent side-cannel attacks. RNS is not only useful for implementing RSA algorithm and Elliptic curve cryptography using Montgomery multiplication and exponentiation, but alsois useful for applications in post quantum cryptographic implementations.

Notable among these are Lattice-based cryptosystems which use thousands of bits of key. While multiprecision arithmetic can be used to implement such big word length operations, RNS is naturally suited to these problems since operation are inherently mapped to several small word length operands.The reader is referred to [16] for a comprehensive tutorial on Application of RNS to Cryptographic system design.

Several RNS based Digital Signal processing applications have been explored for building FIR, IIR filters, FFT engines and implementations on ASIC as well as FPGAs have been continuously being investigated for low power and low area and speed efficient designs. RNS is especially attractive for FIR filters of large taps since all weighting by coefficients and accumulation can be done very efficiently in residue form. Hence, the time taken for input to residue conversion and residue to binary conversion is not significant compared to the advantage gained in fast weighting and accumulation.

More over scaling and stability issues do not arise. RNS is especially attractive for providing tolerance against soft errors. In addition RNS leads to power efficiency due to small word length computations being done in parallel instead of large word length operations. Using special techniques like Quadratic Residue number systems, all transforms such as DCT, DWT (Discrete Wavelet Transform), NTT, FFT have been be efficiently implemented using RNS. RNS has also been used for designing Gaussian smoothing and Sobel’s edge detector in image processing application. RNS has also been used for packet forwarding in Wireless sensor Networks (WSN). Secure file storage in cloud has been accomplished using RNS by dividing the file into residue segments, encrypting and storing on different cloud severs. Other applications include use of RNS for realizing fault tolerant hybrid memories. RNS has been employed in communication systems for code design comprising of information and redundant residues to achieve good error correction capability. The reader is referred to references [17] and [18] for exhaustive treatment of these applications.


[1] R.L. Rivest, A. Shamir, and L.M. Adleman, “A Method for Obtaining Digital Signatures and
Public–Key Cryptosystems,” Communications of the ACM, Vol.. 21, pp. 120–126, Feb 1978.

[2] A. Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers, 1993.

[3] W. Wang, X. Huang, N. Emmart, and C.Weems, VLSI Design of a Large-Number Multiplier for Fully Homomorphic Encryption, Vol.22, pp 1879-1887, 2014.

[4] K. Hwang, Computer Arithmetic: Principles,architecture and Design, Wiley, 1979.

[5] I. Koren, Computer Arithmetic Algorithms, Brookside Court Publishers, Amherst, Massa-
chusetts, 1998.

[6] H. Garner, “The Residue Number system”, IRE Transactions on Electronic Computers, EC-
8, pp 140-147, 1959.

[7] N.Szabo and R.Tanaka, Residue Arithmetic and Its applications in Computer Technology,
New York: McGraw Hill, 1967.

[8] R. Watson and C. Hastings, Residue Arithmetic and Reliable Computer design, Washing-
ton DC, Spartan, 1967.

[9] A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography, by
CRC Press, 1996.

[10] P.L. Montgomery, “Modular multiplication without trial division”, Math. Comput., Vol. 44,
pp 519-521, 1985.

[11]C.K. Koc, T. Acar and B.S. Kaliski.Jr, “Analyzing and comparing Montgomery Multiplica-
tion Algorithms”, IEEE Micro, pp 26-33, 1996.

[12]. M.A. Soderstrand, G.A. Jullien, W.K. Jenkins and F. Taylor (Eds), Residue Number Sys-
tem Arithmetic: Modern Applications in Digital signal Processing, IEEE Press, 1986.

[13] P.V. Ananda Mohan, Residue Number Systems: Algorithms and Architetectures, Kluwer, 2002.

[14] A. R. Omondi and B. Premkumar, Residue mNumber Systems: Theory and implementation,
Imperial College Press, 2007.

[15] J. Fan, F. Vercauteren and I. Verbau- whede, Efficient hardware implementation
of Fp-Arithmetic for Pairing-friendly curves, IEEE Transactions on Computers, Vol. 61, pp
676-685, 2012.

[16] L.Sousa, S.Antao and P.Martins, Combining residue arithmetic to design efficient cryp-
tographic circuits and Systems, IEEE Circuits and Systems Magazine, Vol. 16, Number 4, pp
6-32, 2015.

[17] C.H. Chang, A.S. Molahosseini, A.A.E.Zarandi and T.F. Tay, Residue Number systems:
A new paradigm to datapath optimization for low-power and high-performance Digital signal Processing applications, IEEE Circuits and Systems Magazine, Vol. 15, Number 4, pp 26-44.

[18] P.V Anand Mohan, Residue Number Systems: Theory and Applications, Birkhauser Basel, 2016.

1 2 3 4 5

Leave a Comment:

Your email address will not be published. Required fields are marked *