Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
Języki publikacji
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).
Opis fizyczny
Bibliogr. 34 poz.
  • Jan Dlugosz University in Czestochowa, Armii Krajowej 13/15, 42-200 Czestochowa, Poland
  • [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.
Typ dokumentu
Identyfikator YADDA
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.