An efficient implementation of the Chinese Remainder Theorem in minimally redundant Residue Number System

Mikhail Selianinau

Abstract


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.

Keywords


Residue Number System, Chinese Remainder Theorem, residue code, rank of a number, positional characteristics

Full Text:

PDF

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.




DOI: https://doi.org/10.7494/csci.2020.21.2.3616

Refbacks

  • There are currently no refbacks.