An efficient implementation of the Chinese Remainder Theorem in minimally redundant Residue Number System
DOI:
https://doi.org/10.7494/csci.2020.21.2.3616Keywords:
Residue Number System, Chinese Remainder Theorem, residue code, rank of a number, positional characteristicsAbstract
The Chinese Remainder Theorem (CRT) widely used in many modern computer applications. This paper presents an efficient approach to the calculation of the rank of a number, a principal positional characteristic used in the Residue Number System (RNS). The proposed method does not use large modulo addition operations compared to a straightforward implementation of the CRT algorithm. The rank of a number is equal to a sum of an inexact rank and a two-valued correction factor that only takes on the values 0 or 1. We propose a minimally redundant RNS, which provides low computational complexity of the rank calculation. The effectiveness of the novel method is analyzed concerning conventional non-redundant RNS. Owing to the extension of the residue code, by adding the extra residue modulo 2, the complexity of rank calculation goes down from \(O(k^2)\) to \(O(k)\), where \(k\) equals the number of residues in non-redundant RNS.Downloads
References
Akushskii I., Juditskii D.: Machine Arithmetic in Residue Classes. Sov. Radio, Moscow, 1968.
Amerbayev V.: Theoretical Foundations of Machine Arithmetic. Nauka, Alma-Ata, Kazakh. SSR, 1976.
Burton D.: Elementary Number Theory. Allyn and Bacon, Boston, 1980.
Chernyavsky A., Danilevich V., Kolyada A., Selyaninov M.: High-Speed Methods and Systems of Digital Information Processing. Belarusian State University, Minsk, Belarus, 1996.
Ding C., Pei D., Salomaa A.: Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography. World Scientific Publishing Co., River Edge, NJ, United States, 1996.
Hardy G., Wright E.: An Introduction to the Theory of Numbers. Oxford University Press, Ely House, London, 6 ed., 2008.
Kawamura S., Koike A., Sano F., Shimbo A.: Cox-rower architecture for fast parallel Montgomery multiplication. In: EUROCRYPT’00: Proc. 19th international conference on Theory and application of cryptographic techniques (Bruges, Belgium, May 14 – 18, 2000), pp. 523–538. Springer, Berlin, 2000.
Knuth D.: The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley Longman Publishing Co., Boston, 3 ed., 1997.
Kolyada A., Pak I.: Modular Structures for Pipelining Digital Information Processing. Belarusian State University, Minsk, Belarus, 1992.
Kolyada A., Selyaninov M.: Generation of integral characteristics of symmetric-range residue codes. In: Cybern. Syst. Anal., vol. 22, pp. 431–437, 1986.
Mohan A.: Residue Number Systems. Theory and Applications. Springer, Cham, Switzerland, 2016.
Molahosseini A., Sousa L., Chang C.: Embedded Systems Design with Special Arithmetic and Number Systems. Springer, Cham, Switzerland, 2017.
Nozaki H., Motoyama M., Shimbo A., Kawamura S.: Implementation of RSA Algorithm Based on RNS Montgomery Multiplication. In: CHES 2001: Cryptographic Hardware and Embedded Systems, Third International Workshop (Paris, France, May 14-16, 2001), pp. 364–376. Springer, Berlin, 2001.
Omondi A., Premkumar B.: Residue Number Systems: Theory and Implementation. Imperial College Press, London, 2007.
Shenoy M., Kumaresan R.: A fast and accurate RNS scaling technique for high-speed signal processing. In: IEEE Trans. Acoust. Speech Signal Process., vol. 37, pp. 929–937, 1989.
Shoup V.: A Computational Introduction to Number Theory and Algebra. Cambridge University Press, UK, 2 ed., 2005.
Soderstrand M., Jenkins W., Jullien G., Taylor F.: Residue Number System Arithmetic: Modern Applications in Digital Signal Processing. IEEE Press, Piscataway, NJ, 1986.
Szabo N., Tanaka R.: Residue Arithmetic and Its Application to Computer Technology. McGraw-Hill, New York, 1967.
Vu T.: Efficient implementations of the Chinese Remainder Theorem for sign detection and residue decoding. In: IEEE Trans. Comput., vol. 34, pp. 646–651, 1985.
Downloads
Published
How to Cite
Issue
Section
