Multiple approaches to Convert RNS to Decimal Numbers
DOI:
https://doi.org/10.29304/jqcm.2023.15.3.1276Keywords:
Residues Number System, Chinese Remainder Theorem, Mixed Radix Conversion Method, Approximation Method, Diagonal Function, Base ExtensionAbstract
Improving the performance and speed of encryption algorithms is an important issue in cryptography. One of these improvements is the use of the RNS system. In the research, the RNS system and how to retrieve numbers from the RNS system to WNS weight number system or (decimal number) where discussed in several ways, and after performing multiplication operations, giving illustrative examples and making comparisons between methods.
Downloads
Download data is not yet available.
References
[1] Garner, H. L. The residue number system. In Papers presented at the the March 3-5, 1959, western joint computer conference (pp. 146-153). (1959).
[2] Wu, S., Zhao, C., Yuan, Y., Sun, S., Li, J., & Liu, Y. HLG: A framework for computing graphs in Residue Number System and its application in Fully Homomorphic Encryption. Cryptology ePrint Archive. (2023).
[3] Gomathisankaran, M., Tyagi, A., & Namuduri, K. HORNS: A homomorphic encryption scheme for Cloud Computing using Residue Number System. In 2011 45th Annual Conference on Information Sciences and Systems (pp. 1-5). IEEE. (2011).
[4] Kuchukov, V., Telpukhov, D., Babenko, M., Mkrtchan, I., Stempkovsky, A., Kucherov, N., ... & Grigoryan, M. Performance Analysis of Hardware Implementations of Reverse Conversion from the Residue Number System. Applied Sciences, 12(23), 12355. . (2022).
[5] Bigou, K., & Tisserand, A. Improving modular inversion in RNS using the plus-minus method. In Cryptographic Hardware and Embedded Systems-CHES, 2013: 15th International Workshop, Santa Barbara, CA, USA, August 20-23, 2013. Proceedings 15 (pp. 233-249). Springer Berlin Heidelberg. (2013).
[6] Posch, K. C., & Posch, R. Modulo reduction in residue number systems. IEEE Transactions on Parallel and Distributed Systems, 6(5), 449-454. (1995).
[7] Umar, A. F. Data conversion in Residue Number System. Department of Electrical and Computer Engineering Mc Gill University Montreal. (2011).
[8] Gbolagade, K. A., & Cotofana, S. D. MRC technique for RNS to decimal conversion using the moduli set {2n+ 2, 2n+ 1, 2n}. In PRORISC, Veldhoven, The Netherlands (pp. 318-321). STW. (2008).
[9] Jean C.N. , Kazuhide F. , Thomas P., and Arnaud S. , Generating Very Large RSA Bases . IEEE Trans. Emerg. Topics Comput., early access. (2022).
[10] Bigou, K., & Tisserand, A. Hybrid position-residues number system. In 2016 IEEE 23nd Symposium on Computer Arithmetic (ARITH) (pp. 126-133). IEEE. (2016).
[11] Gbolagade, K. A., & Cotofana, S. D. An O (n) residue number system to mixed radix conversion technique. In 2009 IEEE International Symposium on Circuits and Systems (pp. 521-524). IEEE. (2009).
[12] Chakraborti, Soundararajan, & Reddy. An implementation of mixed-radix conversion for residue number applications. IEEE Transactions on computers, 100(8), 762-764. (1986).
[13] Shiriaev, E., Kucherov, N., Babenko, M., & Nazarov, A. Fast Operation of Determining the Sign of a Number in RNS Using the Akushsky Core Function. Computation, 11(7), 124. (2023).
[14] Babenko, M., & Golimblevskaia, E. About One Property of Number Rank in RNS. In 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus) (pp. 212-216). IEEE. (2021).
[15] Valueva, M., Valuev, G., Semyonova, N., Lyakhov, P., Chervyakov, N., Kaplun, D., & Bogaevskiy, D. Construction of residue number system using hardware efficient diagonal function. Electronics, 8(6), 694. (2019).
[16] Ananda Mohan, P. V. RNS to binary conversion using diagonal function and Pirlo and Impedovo monotonic function. Circuits, Systems, and Signal Processing, 35, 1063-1076. (2016).
[17] Szabo, N. S., & Tanaka, R. I. Residue arithmetic and its applications to computer technology. (1967).
[18] Kawamura, S., Koike, M., Sano, F., & Shimbo, A. Cox-rower architecture for fast parallel montgomery multiplication. In Advances in Cryptology—EUROCRYPT 2000: International Conference on the Theory and Application of Cryptographic Techniques Bruges, Belgium, May 14–18, 2000 Proceedings 19 (pp. 523-538). Springer Berlin Heidelberg. (2000).
[19] Bigou, K., & Tisserand, A. RNS modular multiplication through reduced base extensions. In 2014 IEEE 25th International Conference on Application-Specific Systems, Architectures and Processors (pp. 57-62). IEEE. (2014).
[2] Wu, S., Zhao, C., Yuan, Y., Sun, S., Li, J., & Liu, Y. HLG: A framework for computing graphs in Residue Number System and its application in Fully Homomorphic Encryption. Cryptology ePrint Archive. (2023).
[3] Gomathisankaran, M., Tyagi, A., & Namuduri, K. HORNS: A homomorphic encryption scheme for Cloud Computing using Residue Number System. In 2011 45th Annual Conference on Information Sciences and Systems (pp. 1-5). IEEE. (2011).
[4] Kuchukov, V., Telpukhov, D., Babenko, M., Mkrtchan, I., Stempkovsky, A., Kucherov, N., ... & Grigoryan, M. Performance Analysis of Hardware Implementations of Reverse Conversion from the Residue Number System. Applied Sciences, 12(23), 12355. . (2022).
[5] Bigou, K., & Tisserand, A. Improving modular inversion in RNS using the plus-minus method. In Cryptographic Hardware and Embedded Systems-CHES, 2013: 15th International Workshop, Santa Barbara, CA, USA, August 20-23, 2013. Proceedings 15 (pp. 233-249). Springer Berlin Heidelberg. (2013).
[6] Posch, K. C., & Posch, R. Modulo reduction in residue number systems. IEEE Transactions on Parallel and Distributed Systems, 6(5), 449-454. (1995).
[7] Umar, A. F. Data conversion in Residue Number System. Department of Electrical and Computer Engineering Mc Gill University Montreal. (2011).
[8] Gbolagade, K. A., & Cotofana, S. D. MRC technique for RNS to decimal conversion using the moduli set {2n+ 2, 2n+ 1, 2n}. In PRORISC, Veldhoven, The Netherlands (pp. 318-321). STW. (2008).
[9] Jean C.N. , Kazuhide F. , Thomas P., and Arnaud S. , Generating Very Large RSA Bases . IEEE Trans. Emerg. Topics Comput., early access. (2022).
[10] Bigou, K., & Tisserand, A. Hybrid position-residues number system. In 2016 IEEE 23nd Symposium on Computer Arithmetic (ARITH) (pp. 126-133). IEEE. (2016).
[11] Gbolagade, K. A., & Cotofana, S. D. An O (n) residue number system to mixed radix conversion technique. In 2009 IEEE International Symposium on Circuits and Systems (pp. 521-524). IEEE. (2009).
[12] Chakraborti, Soundararajan, & Reddy. An implementation of mixed-radix conversion for residue number applications. IEEE Transactions on computers, 100(8), 762-764. (1986).
[13] Shiriaev, E., Kucherov, N., Babenko, M., & Nazarov, A. Fast Operation of Determining the Sign of a Number in RNS Using the Akushsky Core Function. Computation, 11(7), 124. (2023).
[14] Babenko, M., & Golimblevskaia, E. About One Property of Number Rank in RNS. In 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus) (pp. 212-216). IEEE. (2021).
[15] Valueva, M., Valuev, G., Semyonova, N., Lyakhov, P., Chervyakov, N., Kaplun, D., & Bogaevskiy, D. Construction of residue number system using hardware efficient diagonal function. Electronics, 8(6), 694. (2019).
[16] Ananda Mohan, P. V. RNS to binary conversion using diagonal function and Pirlo and Impedovo monotonic function. Circuits, Systems, and Signal Processing, 35, 1063-1076. (2016).
[17] Szabo, N. S., & Tanaka, R. I. Residue arithmetic and its applications to computer technology. (1967).
[18] Kawamura, S., Koike, M., Sano, F., & Shimbo, A. Cox-rower architecture for fast parallel montgomery multiplication. In Advances in Cryptology—EUROCRYPT 2000: International Conference on the Theory and Application of Cryptographic Techniques Bruges, Belgium, May 14–18, 2000 Proceedings 19 (pp. 523-538). Springer Berlin Heidelberg. (2000).
[19] Bigou, K., & Tisserand, A. RNS modular multiplication through reduced base extensions. In 2014 IEEE 25th International Conference on Application-Specific Systems, Architectures and Processors (pp. 57-62). IEEE. (2014).
Downloads
Published
2023-09-30
How to Cite
Jawad, N. H., & Abdulhadi, S. (2023). Multiple approaches to Convert RNS to Decimal Numbers. Journal of Al-Qadisiyah for Computer Science and Mathematics, 15(3), Comp Page 108–114. https://doi.org/10.29304/jqcm.2023.15.3.1276
Issue
Section
Computer Articles
