{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T10:39:52Z","timestamp":1762079992691,"version":"build-2065373602"},"reference-count":51,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2022,12,14]],"date-time":"2022-12-14T00:00:00Z","timestamp":1670976000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In this paper, we consider one of the key problems in modular arithmetic. It is known that scaling in the residue number system (RNS) is a rather complicated non-modular procedure, which requires expensive and complex operations at each iteration. Hence, it is time consuming and needs too much hardware for implementation. We propose a novel approach to power-of-two scaling based on the Chinese Remainder Theorem (CRT) and rank form of the number representation in RNS. By using minimal redundancy of residue code, we optimize and speed up the rank calculation and parity determination of divisible integers in each iteration. The proposed enhancements make the power-of-two scaling simpler and faster than the currently known methods. After calculating the rank of the initial number, each iteration of modular scaling by two is performed in one modular clock cycle. The computational complexity of the proposed method of scaling by a constant Sl=2l associated with both required modular addition operations and lookup tables is estimeted as k and 2k+1, respectively, where k equals the number of primary non-redundant RNS moduli. The time complexity is log2k+l modular clock cycles.<\/jats:p>","DOI":"10.3390\/e24121824","type":"journal-article","created":{"date-parts":[[2022,12,15]],"date-time":"2022-12-15T01:52:30Z","timestamp":1671069150000},"page":"1824","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["An Efficient CRT-Base Power-of-Two Scaling in Minimally Redundant Residue Number System"],"prefix":"10.3390","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5669-701X","authenticated-orcid":false,"given":"Mikhail","family":"Selianinau","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Sciences, Faculty of Science and Technology, Jan Dlugosz University in Czestochowa, al. Armii Krajowej 13\/15, 42-200 Czestochowa, Poland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7492-5394","authenticated-orcid":false,"given":"Yuriy","family":"Povstenko","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Sciences, Faculty of Science and Technology, Jan Dlugosz University in Czestochowa, al. Armii Krajowej 13\/15, 42-200 Czestochowa, Poland"}]}],"member":"1968","published-online":{"date-parts":[[2022,12,14]]},"reference":[{"key":"ref_1","unstructured":"Akushskii, I.Y., and Juditskii, D.I. (1968). Machine Arithmetic in Residue Classes, Soviet Radio. (In Russian)."},{"key":"ref_2","unstructured":"Amerbayev, V.M. (1976). Theoretical Foundations of Machine Arithmetic, Nauka. (In Russian)."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Omondi, A.R., and Premkumar, B. (2007). Residue Number Systems: Theory and Implementation, Imperial College Press.","DOI":"10.1142\/9781860948671"},{"key":"ref_4","unstructured":"Szabo, N.S., and Tanaka, R.I. (1967). Residue Arithmetic and Its Application to Computer Technology, McGraw-Hill."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Molahosseini, A.S., de Sousa, L.S., and Chang, C.H. (2017). Embedded Systems Design with Special Arithmetic and Number Systems, Springer.","DOI":"10.1007\/978-3-319-49742-6"},{"key":"ref_6","unstructured":"Soderstrand, M.A., Jenkins, W.K., Jullien, G.A., and Taylor, F.J. (1986). Residue Number System Arithmetic: Modern Applications in Digital Signal Processing, IEEE Press."},{"key":"ref_7","unstructured":"Chernyavsky, A.F., Danilevich, V.V., Kolyada, A.A., and Selyaninov, M.Y. (1996). High-Speed Methods, and Systems of Digital Information Processing, Belarusian State University. (In Russian)."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Ananda Mohan, P.V. (2016). Residue Number Systems. Theory and Applications, Springer.","DOI":"10.1007\/978-3-319-41385-3"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Ding, C., Pei, D., and Salomaa, A. (1996). Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography, World Scientific.","DOI":"10.1142\/9789812779380"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Omondi, A.R. (2020). Cryptography Arithmetic: Algorithms and Hardware Architectures, Springer.","DOI":"10.1007\/978-3-030-34142-8"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0898-1221(90)90190-U","article-title":"A new residue number division algorithm","volume":"19","author":"Chren","year":"1990","journal-title":"Comput. Math. Appl."},{"key":"ref_12","unstructured":"Chiang, J.-S., and Lu, M. A general division algorithm for the Residue Number System. Proceedings of the 10th IEEE Symposium on Computer Arithmetic, Grenoble, France, 26\u201328 June 1991."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1109\/12.156545","article-title":"A novel division algorithm for Residue Number Systems","volume":"41","author":"Lu","year":"1992","journal-title":"IEEE Trans. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1109\/12.403714","article-title":"Integer division in residue number systems","volume":"44","author":"Hitz","year":"1995","journal-title":"IEEE Trans. Comput."},{"key":"ref_15","unstructured":"Hiasat, A.A., and Abdel-Aty-Zohdy, H.S. Design and implementation of an RNS division algorithm. Proceedings of the 13th IEEE Symposium on Computer Arithmetic, Asilomar, CA, USA, 6\u20139 July 1997."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1023\/A:1008065819322","article-title":"A new Euclidean division algorithm for residue number systems","volume":"19","author":"Bajard","year":"1998","journal-title":"J. VLSI Signal Process. Syst. Signal Image Video Technol."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1080\/00207160410001708805","article-title":"A high-speed division algorithm in residue number system using parity-checking technique","volume":"81","author":"Yang","year":"2004","journal-title":"Int. J. Comput. Math."},{"key":"ref_18","first-page":"368","article-title":"A division algorithm for residue numbers","volume":"172","author":"Chang","year":"2006","journal-title":"Appl. Math. Comput."},{"key":"ref_19","first-page":"59","article-title":"A division algorithm using bisection method in residue number system","volume":"2","author":"Chang","year":"2013","journal-title":"Int. J.Comput. Consum. Control (IJ3C)"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0898-1221(94)90052-3","article-title":"An approximate sign detection method for residue numbers and its application to RNS division","volume":"27","author":"Hung","year":"1994","journal-title":"Comput. Math. Appl."},{"key":"ref_21","unstructured":"Burton, D.M. (2011). Elementary Number Theory, McGraw-Hill. [7th ed.]."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Hardy, G.H., and Wright, E.M. (2008). An Introduction to the Theory of Numbers, Oxford University Press. [6th ed.].","DOI":"10.1093\/oso\/9780199219858.001.0001"},{"key":"ref_23","unstructured":"Knuth, D.E. (1998). The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Addison-Wesley. [3rd ed.]."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Shoup, V. (2005). A Computational Introduction to Number Theory and Algebra, Cambridge University Press. [2nd ed.].","DOI":"10.1017\/CBO9781139165464"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1109\/12.16508","article-title":"Fast base extension using a redundant modulus in RNS","volume":"38","author":"Shenoy","year":"1989","journal-title":"IEEE Trans. Comput."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/j.jpdc.2016.06.005","article-title":"New distributed algorithms for fast sign detection in residue number systems (RNS)","volume":"97","author":"Phatak","year":"2016","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_27","first-page":"646","article-title":"Efficient implementations of the Chinese Remainder Theorem for sign detection and residue decoding","volume":"34","author":"Vu","year":"1985","journal-title":"IEEE Trans. Comput."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Kawamura, S., Koike, M., Sano, F., and Shimbo, A. Cox-rower architecture for fast parallel Montgomery multiplication. Proceedings of the EUROCRYPT\u201900: 19th International Conference on Theory and Application of Cryptographic Techniques, Bruges, Belgium, 14\u201318 May 2000.","DOI":"10.1007\/3-540-45539-6_37"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Nozaki, H., Motoyama, M., Shimbo, A., and Kawamura, S. Implementation of RSA algorithm based on RNS Montgomery multiplication. Proceedings of the CHES 2001: Cryptographic Hardware and Embedded Systems, Third International Workshop, Paris, France, 6\u201314 May 2001.","DOI":"10.1007\/3-540-44709-1_30"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1850004","DOI":"10.1142\/S0218126618500044","article-title":"Interval estimation of relative values in Residue Number System","volume":"27","author":"Isupov","year":"2018","journal-title":"J. Circuits, Syst. Comput."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1080","DOI":"10.1016\/j.future.2017.09.061","article-title":"AR-RRNS: Configurable reliable distributed data storage systems for Internet of Things to ensure security","volume":"92","author":"Chervyakov","year":"2019","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_32","first-page":"83","article-title":"An improved RNS variant of the BFV homomorphic encryption scheme","volume":"Volume 11405","author":"Halevi","year":"2019","journal-title":"Topics in Cryptology\u2013CT-RSA 2019, Proceedings of the Cryptographers\u2019 Track at the RSA Conference, San Francisco, CA, USA, 4\u20138 March 2019"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"237","DOI":"10.7494\/csci.2020.21.2.3616","article-title":"An efficient implementation of the Chinese Remainder Theorem in minimally redundant Residue Number System","volume":"21","author":"Selianinau","year":"2020","journal-title":"Comput. Sci."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1117","DOI":"10.1007\/s00224-021-10035-y","article-title":"Computationally efficient approach to implementation of the Chinese Remainder Theorem algorithm in minimally redundant Residue Number System","volume":"65","author":"Selianinau","year":"2021","journal-title":"Theory Comput. Syst."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1109\/TC.1978.1675105","article-title":"Residue number scaling and other operations using ROM arrays","volume":"27","author":"Jullien","year":"1978","journal-title":"IEEE Trans. Comput."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1109\/ASSP.1989.28063","article-title":"A fast and accurate RNS scaling technique for high speed signal processing","volume":"37","author":"Shenoy","year":"1989","journal-title":"IEEE Trans. Acoust. Speech Signal Process."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"2427","DOI":"10.1109\/78.469842","article-title":"Fast base extension and precise scaling in RNS for look-up table implementation","volume":"43","author":"Barsi","year":"1995","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"748","DOI":"10.1109\/12.780883","article-title":"A look up scheme for scaling in the RNS","volume":"48","author":"Garsia","year":"1999","journal-title":"IEEE Trans. Comput."},{"key":"ref_39","unstructured":"Griffin, M., Sousa, M., and Taylor, F. Efficient scaling in the residue number system. Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, Glasgow, UK, 23\u201326 May 1989."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1007\/BF01075217","article-title":"Scaling in residue number systems","volume":"25","author":"Vasilevich","year":"1989","journal-title":"Cybern. Syst. Anal."},{"key":"ref_41","first-page":"132","article-title":"Scaling methods in minimally redundant modular arithmetic","volume":"4","author":"Chernyavsky","year":"1998","journal-title":"Proc. Natl. Acad. Sci. Belarus Phys. Math. Ser."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1109\/TVLSI.2003.810799","article-title":"New power-of-2 RNS scaling scheme for cell-based IC design","volume":"11","author":"Stouraitis","year":"2003","journal-title":"IEEE Trans. VLSI Syst."},{"key":"ref_43","unstructured":"Cardarilli, G.C., Del Re, A., Nannarelli, A., and Re, M. Programmable power-of-two RNS scaler and its application to a QRNS polyphase filter. Proceedings of the IEEE International Symposium on Circuits and Systems, Kobe, Japan, 23\u201326 May 2005."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Isupov, K., Knyazkov, V., and Kuvaev, A. Fast power-of-two RNS scaling algorithm for large dynamic ranges. Proceedings of the 2017 IVth International Conference on Engineering and Telecommunication (EnT), Moscow, Russia, 29\u201330 November 2017.","DOI":"10.1109\/ICEnT.2017.36"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1109\/TCS.1985.1085714","article-title":"A modified definition of symmetric RNS improving scaling and overflow detection","volume":"32","author":"Clemens","year":"1985","journal-title":"IEEE Trans. Circuits Syst."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"3322","DOI":"10.1109\/TC.2015.2401026","article-title":"2n RNS scalers for extended 4-moduli sets","volume":"64","author":"Sousa","year":"2015","journal-title":"IEEE Trans. Comput."},{"key":"ref_47","first-page":"21","article-title":"RNS scaling algorithm for a new moduli set {22n+1 + 1,22n+1,22n+1 \u2212 1}","volume":"165","author":"Mustapha","year":"2017","journal-title":"Int. J. Comput. Appl."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1109\/TC.2017.2652474","article-title":"Efficient RNS scalers for the extended three-moduli set {2n \u2212 1,2n+p,2n + 1}","volume":"66","author":"Hiasat","year":"2017","journal-title":"IEEE Trans Comput."},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Hiasat, A. (2018). New residue number system scaler for the three-moduli set {2n+1 \u2212 1,2n,2n \u2212 1}. Computers, 3.","DOI":"10.3390\/computers7030046"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"2050041","DOI":"10.1142\/S0218126620500413","article-title":"A scaler design for the RNS three-moduli set {2n+1 \u2212 1,2n,2n \u2212 1} based on mixed-radix conversion","volume":"29","author":"Hiasat","year":"2020","journal-title":"J. Circuits. Syst. Comput."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"596","DOI":"10.4218\/etrij.2018-0408","article-title":"Efficient programmable power-of-two scaler for the three-moduli set {2n+p,2n \u2212 1,2n+1 \u2212 1}","volume":"42","author":"Taheri","year":"2020","journal-title":"ETRI J."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/12\/1824\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:41:23Z","timestamp":1760146883000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/12\/1824"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,14]]},"references-count":51,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2022,12]]}},"alternative-id":["e24121824"],"URL":"https:\/\/doi.org\/10.3390\/e24121824","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2022,12,14]]}}}