{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T08:04:17Z","timestamp":1771488257794,"version":"3.50.1"},"reference-count":27,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T00:00:00Z","timestamp":1559088000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>Modular reduction of large values is a core operation in most common public-key cryptosystems that involves intensive computations in finite fields. Within such schemes, efficiency is a critical issue for the effectiveness of practical implementation of modular reduction. Recently, Residue Number Systems have drawn attention in cryptography application as they provide a good means for extreme long integer arithmetic and their carry-free operations make parallel implementation feasible. In this paper, we present an algorithm to calculate the precise value of \u201c X mod p \u201d directly in the RNS representation of an integer. The pipe-lined, non-pipe-lined, and parallel hardware architectures are proposed and implemented on XILINX FPGAs.<\/jats:p>","DOI":"10.3390\/cryptography3020014","type":"journal-article","created":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T11:31:28Z","timestamp":1559129488000},"page":"14","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Improved Sum of Residues Modular Multiplication Algorithm"],"prefix":"10.3390","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3984-5361","authenticated-orcid":false,"given":"Mohamad Ali","family":"Mehrabi","sequence":"first","affiliation":[{"name":"Department of Computing, Macquarie University, Sydney 2109, Australia"}]}],"member":"1968","published-online":{"date-parts":[[2019,5,29]]},"reference":[{"key":"ref_1","first-page":"247","article-title":"Circuit operators","volume":"3","author":"Svobod","year":"1957","journal-title":"Inf. Process. Mach."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Garner, H.L. (1959, January 3\u20135). The Residue Number System. Proceedings of the Western Joint Computer Conference, Francisco, CA, USA.","DOI":"10.1145\/1457838.1457864"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Mohan, P.V.A. (2016). Residue Number Systems: Theory and Applications, Springer.","DOI":"10.1007\/978-3-319-41385-3"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A method for obtaining digital signatures and public key cryptosystems","volume":"21","author":"Rivest","year":"1978","journal-title":"Comm. ACM"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1109\/TC.2004.2","article-title":"A full RNS implementation of RSA","volume":"53","author":"Bajard","year":"2004","journal-title":"IEEE Trans. Comput."},{"key":"ref_6","first-page":"975","article-title":"Efficient Algorithm for RNS Implementation of RSA","volume":"127","author":"Fadulilahi","year":"2015","journal-title":"Int. J. Comput. Appl."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1109\/71.382314","article-title":"Modulo reduction in residue number systems","volume":"6","author":"Posch","year":"1995","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1090\/S0025-5718-1985-0777282-X","article-title":"Modular Multiplication Without Trial Division","volume":"44","author":"Montgomery","year":"1985","journal-title":"Math. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"766","DOI":"10.1109\/12.709376","article-title":"An RNS Montgomery modular multiplication algorithm","volume":"47","author":"Bajard","year":"1998","journal-title":"IEEE Trans. Comput."},{"key":"ref_10","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_11","unstructured":"Bajard, J.C., Didier, L.S., and Kornerup, P. (2001, January 11\u201313). Modular Multiplication and Base Extensions in Residue Number Systems. Proceedings of the 15th IEEE Symposium on Computer Arithmetic, Vail, CO, USA."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Kawamura, S., Koike, M., Sano, F., and Shimbo, A. (2000, January 14\u201318). Cox-Rower Architecture for Fast Parallel Montgomery Multiplication. Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, Bruges, Belgium.","DOI":"10.1007\/3-540-45539-6_37"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Bajard, J.C., and Merkiche, N. (2014, January 5\u20137). Double Level Montgomery Cox-Rower Architecture, New Bounds. Proceedings of the 13th Smart Card Research and Advanced Application Conference, Paris, France.","DOI":"10.1007\/978-3-319-16763-3_9"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/s13389-017-0154-9","article-title":"Montgomery reduction within the context of residue number system arithmetic","volume":"8","author":"Bajard","year":"2018","journal-title":"J. Cryptogr. Eng."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1545","DOI":"10.1109\/TVLSI.2012.2210916","article-title":"Efficient RNS implementation of elliptic curve point multiplication over GF(p)","volume":"21","author":"Esmaeildoust","year":"2012","journal-title":"IEEE Trans. Very Larg. Scale Integr. Syst."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Guillermin, N. (2010, January 17\u201320). A High Speed Coprocessor for Elliptic Curve Scalar Multiplications over Fp. Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems, Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-642-15031-9_4"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Schinianakis, D., and Stouraitis, T. (2011, January 15\u201318). A RNS Montgomery Multiplication Architecture. Proceedings of the IEEE International Symposium of Circuits and Systems (ISCAS), Rio de Janeiro, Brazil.","DOI":"10.1109\/ISCAS.2011.5937776"},{"key":"ref_18","first-page":"1","article-title":"RNS Montgomery reduction algorithms using quadratic residutory","volume":"1","author":"Kawamura","year":"2018","journal-title":"J. Cryptogr. Eng."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s00200-010-0124-2","article-title":"Highly parallel modular multiplication in the residue number system using sum of residues reduction","volume":"21","author":"Phillips","year":"2010","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1027","DOI":"10.1007\/s00034-016-0336-1","article-title":"Highly Parallel Modular Multiplier for Elliptic Curve Cryptography in Residue Number System","volume":"36","author":"Asif","year":"2017","journal-title":"Circuits Syst. Signal Process."},{"key":"ref_21","unstructured":"(2019, May 01). Standards for Efficient Cryptography SEC2: Recommended Elliptic Curve Domain Parameters. Version 2.0 CERTICOM Corp. 27 January 2010. Available online: https:\/\/www.secg.org\/sec2-v2.pdf."},{"key":"ref_22","unstructured":"(2019, May 01). Ed25519: High-Speed High-Security Signatures. Available online: https:\/\/ed25519.cr.yp.to\/."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Bajard, J.C., Kaihara, M.E., and Plantard, T. (2009, January 8\u201310). Selected RNS bases for modular multiplication. Proceedings of the 19th IEEE Symposium on Computer Arithmetic, Portland, OR, USA.","DOI":"10.1109\/ARITH.2009.20"},{"key":"ref_24","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_25","unstructured":"Barrett, P. (1986, January 20\u201322). Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor. Proceedings of the Conference on the Theory and Application of Cryptographic Techniques, Linkoping, Sweden."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/j.vlsi.2017.11.010","article-title":"A Fully RNS based ECC Processor","volume":"61","author":"Asif","year":"2018","journal-title":"Integration"},{"key":"ref_27","unstructured":"Asif, S. (2016). High-Speed Low-Power Modular Arithmetic for Elliptic Curve Cryptosystems Based on the Residue Number System. [Ph.D. Thesis, Macquarie University]."}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/3\/2\/14\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:54:33Z","timestamp":1760187273000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/3\/2\/14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,29]]},"references-count":27,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2019,6]]}},"alternative-id":["cryptography3020014"],"URL":"https:\/\/doi.org\/10.3390\/cryptography3020014","relation":{},"ISSN":["2410-387X"],"issn-type":[{"value":"2410-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,29]]}}}