Efficient implementation of Chinese remainder theorem in minimally redundant residue number system

• Autorzy: Selianinau Mikhail

Identyfikatory

DOI

10.7494/csci.2020.21.2.3616

• Języki publikacji: EN

Abstrakty

EN

The Chinese remainder theorem is 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 that is used in the residue number system. The proposed method does not use large modulo addition operations as compared to a straightforward implementation of the Chinese remainder theorem algorithm. The rank of a number is equal to the sum of an inexact rank and a two-valued correction factor that only takes on values of 0 or 1. We propose a minimally redundant residue number system that provides a low computational complexity of the rank calculation. The effectiveness of the novel method is analyzed regarding a conventional non-redundant residue number system. Owing to the extension of the residue code, the complexity of the rank calculation goes down from O(k2) to O(k) by adding the extra residue modulo 2 (where k equals the number of non-redundant residues).

Słowa kluczowe

EN

residue number system; Chinese remainder theorem; residue code; rank of a number; positional characteristics

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2020
• Tom: T. 21 (2)
• Strony: 237--252
• Opis fizyczny: Bibliogr. 34 poz.

Twórcy

autor

Selianinau Mikhail

• Jan Dlugosz University in Czestochowa, Armii Krajowej 13/15, 42-200 Czestochowa, Poland

Bibliografia

• [1] Abdul-Mumin S., Gbolagade K.A.: Rivest Shamir Adleman Encryption Scheme Based on the Chinese Remainder Theorem, Advances in Networks, vol. 6(1), pp. 40–47, 2018.
• [2] Akushskii I.Y., Juditskii D.I.: Machine Arithmetic in Residue Classes [in Russian], Sovetskoe Radio, Moscow, 1968.
• [3] Amerbayev V.M.: Theoretical Foundations of Machine Arithmetic, Nauka, Alma- -Ata, Kazakh. SSR, 1976.
• [4] Aremu I.A., Gbolagade K.A.: Redundant Residue Number System Based Multiple Error Detection and Correction Using Chinese Remainder Theorem, Software Engineering, vol. 5(5), pp. 72–80, 2017
• [5] Bajard J.C., Eynard J., Merkiche N.: Montgomery reduction within the context of residue number system arithmetic, Journal of Cryptographic Engineering, vol. 8(3), pp. 189–200, 2018.
• [6] Burton D.M.: Elementary Number Theory. Allyn and Bacon, Boston, 1980.
• [7] Chernyavsky A.F., Danilevich V.V., Kolyada A.A., Selyaninov M.Y.: High-Speed Methods and Systems of Digital Information Processing. Belarusian State University, Minsk, Belarus, 1996.
• [8] Courtois J., Abbas-Turki L.A., Bajard J.C.: Resilience of Randomized RNS Arithmetic With Respect to Side-Channel Leaks of Cryptographic Computation, IEEE Transactions on Computers, vol. 68(12), pp. 1720–1730, 2019.
• [9] Ding C., Pei D., Salomaa A.: Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography. World Scientific Publishing Co., River Edge, NJ, United States, 1996.
• [10] Duseja T., Deshmukh M.: Image compression and encryption using chinese remainder theorem, Multimedia Tools and Applications, vol. 78(3), pp. 16727–16753, 2019.
• [11] Hardy G.H., Wright E.M., Wiles A.: An Introduction to the Theory of Numbers. Oxford University Press, Ely House, London, 6 ed., 2008.
• [12] Hsiao T.C., Huang Y.T., Huang Y.M., Chen T.L., Chen T.S., Wang S.D.: Efficient and Scalable Access Management Scheme Based on Chinese Remainder Theorem, Sensors and Materials, vol. 30(3), pp. 413–422, 2018.
• [13] Ibrahim M.B., Gbolagade K.A.: A Chinese Remainder Theorem Based Enhancements of Lempel-ziv-welch and Huffman Coding Image Compression, Asian Journal of Research in Computer Science, vol. 3(3), pp. 1–9, 2019.
• [14] Jakubski A.: Selected application of the Chinese Remainder Theorem in multiparty computation, Journal of Applied Mathematics and Computational Mechanics, vol. 15(1), pp. 39–47, 2016.
• [15] Jia X., Song Y., Wang D., Niel D., Wu J.: A collaborative secret sharing scheme based on the Chinese Remainder Theorem, Mathematical Biosciences and Engineering, vol. 16(3), pp. 1280–1299, 2019.
• [16] Kawamura S., Koike M., Sano F., Shimbo A.: Cox-Rower Architecture for Fast Parallel Montgomery Multiplication. In: EUROCRYPT’00: Proceedings 19th International Conference on Theory and Application of Cryptographic Techniques (Bruges, Belgium, May 14–18, 2000), pp. 523–538. Springer, Berlin, 2000.
• [17] Kirankumar V., Ramasubbareddy S., Kannayaram G., Vishalo G., Nikhil K.: Enhanced Security Using Rivest, Shamir, and Adelman With Chinese Remainder Theorem, Journal of Computational and Theoretical Nanoscience, vol. 16(5-6), pp. 2018–2021, 2019.
• [18] Knuth D.E.: The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Addison-Wesley Longman Publishing Co., Boston, 3 ed., 1997.
• [19] Kolyada A.A., Pak I.T.: Modular Structures for Pipelining Digital Information Processing, Belarusian State University, Minsk, Belarus, 1992.
• [20] Kolyada A.A., Selyaninov M.Y.: Generation of integral characteristics of symmetric-range residue codes, Cybernetics and Systems Analysis, vol. 22(4), pp. 431–437, 1986.
• [21] Madandola T.N., Gbolagade K.A., Yusuf-Asaju A.W.: Effect of Chinese Remainder Theorem on Principal Component Analysis, International Journal of Scientific & Engineering Research, vol. 10(7), pp. 2142–2148, 2019.
• [22] Meng K., Miao F., Huang W., Xiong Y.: Tightly coupled multi-group threshold secret sharing based on Chinese Remainder Theorem, Discrete Applied Mathematics, vol. 268, pp. 152–163, 2019.
• [23] Mohan P.V.A.: Residue Number Systems. Theory and Applications, Springer, Cham, Switzerland, 2016.
• [24] Molahosseini A., Sousa de L.S., Chang C.H.: Embedded Systems Design with Special Arithmetic and Number Systems, Springer, Cham, Switzerland, 2017.
• [25] Niyi M.T., Gbolagade K.A.: Reducing computational Time of Principal Component Analysis with Chinese Remainder Theorem, International Journal of Discrete Mathematics, vol. 4(1), pp. 1–7, 2019.
• [26] 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.
• [27] Omondi A.R., Premkumar B.: Residue Number Systems: Theory and Implementation, Imperial College Press, London, 2007.
• [28] Sheikhi-Garjan M., Bahramian M., Doche C.: Threshold verifiable multi-secret sharing based on elliptic curves and Chinese remainder theorem, IET Information Security, vol. 13(3), pp. 278–284, 2019.
• [29] Shenoy M.A., Kumaresan R.: A fast and accurate RNS scaling technique for high speed signal processing, IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 37, pp. 929–937, 1989.
• [30] Shoup V.: A Computational Introduction to Number Theory and Algebra, Cambridge University Press, UK, 2 ed., 2005.
• [31] Soderstrand M.A., Jenkins W.K., Jullien G.A., Taylor F.J.: Residue Number System Arithmetic: Modern Applications in Digital Signal Processing, IEEE Press, Piscataway, NJ, 1986.
• [32] Szabo N.S., Tanaka R.I.: Residue Arithmetic and Its Application to Computer Technology, McGraw-Hill, New York, 1967.
• [33] Vu T.V.: Efficient Implementations of the Chinese Remainder Theorem for Sign Detection and Residue Decoding, IEEE Transactions on Computers, vol. C-34(7), pp. 646–651, 1985.
• [34] Yan X., Lu Y., Liu L., Liu J., Yang G.: Chinese remainder theorem-based two-in- -one image secret sharing with three decoding options, Digital Signal Processing, vol. 82, pp. 80–90, 2018.