{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T13:13:27Z","timestamp":1753881207361,"version":"3.41.2"},"reference-count":33,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2010,11,30]],"date-time":"2010-11-30T00:00:00Z","timestamp":1291075200000},"content-version":"vor","delay-in-days":333,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Journal of Electrical and Computer Engineering"],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>In the 1980s, when the introduction of public key cryptography spurred interest in modular multiplication, many implementations performed modular multiplication using a sum of residues. As the field matured, sum of residues modular multiplication lost favor to the extent that all recent surveys have either overlooked it or incorporated it within a larger class of reduction algorithms. In this paper, we present a new taxonomy of modular multiplication algorithms. We include sum of residues as one of four classes and argue why it should be considered different to the other, now more common, algorithms. We then apply techniques developed for other algorithms to reinvigorate sum of residues modular multiplication. We compare FPGA implementations of modular multiplication up to 24 bits wide. The sum of residues multipliers demonstrate reduced latency at nearly 50% compared to Montgomery architectures at the cost of nearly doubled circuit area. The new multipliers are useful for systems based on the Residue Number System (RNS).<\/jats:p>","DOI":"10.1155\/2010\/657076","type":"journal-article","created":{"date-parts":[[2010,11,30]],"date-time":"2010-11-30T19:35:30Z","timestamp":1291145730000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Revisiting Sum of Residues Modular Multiplication"],"prefix":"10.1155","volume":"2010","author":[{"given":"Yinan","family":"Kong","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Braden","family":"Phillips","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2010,11,30]]},"reference":[{"key":"e_1_2_7_1_2","doi-asserted-by":"crossref","unstructured":"BarrettP. Implementing the Rivest Shamir and Adleman public-keyencryption algorithm on a standard digital signal processor 263 Proceedings of the Advancesin Cryptology (Crypto \u203286) 1986 311\u2013323 Lecture Notes in Computer Science.","DOI":"10.1007\/3-540-47721-7_24"},{"key":"e_1_2_7_2_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1985-0777282-X"},{"key":"e_1_2_7_3_2","doi-asserted-by":"publisher","DOI":"10.1049\/el:19950217"},{"key":"e_1_2_7_4_2","doi-asserted-by":"crossref","DOI":"10.1049\/el:19891115","article-title":"Bit-serial modular multiplier","volume":"25","author":"Tomlinson A.","year":"1989","journal-title":"Electronics Letters"},{"key":"e_1_2_7_5_2","doi-asserted-by":"crossref","unstructured":"BrickellE. F. A fast modular multiplication algorithm with application to two key cryptography Proceedings of the Advancesin Cryptology (Crypto \u203282) 1982 51\u201360 Lecture Notes in Computer Science.","DOI":"10.1007\/978-1-4757-0602-4_5"},{"key":"e_1_2_7_6_2","unstructured":"SoderstrandM. A. JenkinsW. andJullienG. Residue Number System Arithmetic: Modern Applications\u2014Digital Signal Processing 1986."},{"key":"e_1_2_7_7_2","doi-asserted-by":"crossref","unstructured":"BhardwajM.andLjusaninB. The renaissance\u2014a residue number system based vector co-processor 2 Proceedings of the 32nd Asilomar Conferenceon Signals Systems & Computers 1998 202\u2013207.","DOI":"10.1109\/ACSSC.1998.750854"},{"key":"e_1_2_7_8_2","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/S0045-7906(97)00033-5","article-title":"Optimal VLSI complexity design for high speed pipeline FFT using RNS","volume":"24","author":"Alia G.","year":"1998","journal-title":"Computers and Electrical Engineering"},{"key":"e_1_2_7_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2004.2"},{"key":"e_1_2_7_10_2","doi-asserted-by":"crossref","unstructured":"BajardJ.-C. DidierL.-S. andKornerupP. Modular multiplication and base extensions in residue number systems 2 Proceedings of the 15th IEEE Symposium on Computer Arithmetic 2001 59\u201365.","DOI":"10.1109\/ARITH.2001.930104"},{"volume-title":"Residue Arithmetic and Its Applications to Computer Technology","year":"1967","author":"Szabo N. S.","key":"e_1_2_7_11_2"},{"key":"e_1_2_7_12_2","doi-asserted-by":"crossref","unstructured":"KawamuraS.-I.andHiranoK. A fast modular arithmetic algorithmusing a residue table 330 Proceedings of the Advances in Cryptology (Eurocrypt \u203288) 1988 245\u2013250 Lecture Notes in Computer Science.","DOI":"10.1007\/3-540-45961-8_21"},{"key":"e_1_2_7_13_2","doi-asserted-by":"crossref","unstructured":"FindlayP. A.andJohnsonB. A. Modular exponentiation using recursivesums of residues 435 Proceedings of the Advancesin Cryptology (Crypto \u203289) 1989 371\u2013386 Lecture Notes in Computer Science.","DOI":"10.1007\/0-387-34805-0_35"},{"key":"e_1_2_7_14_2","unstructured":"SuF. F.andHwangT. Comments on iterative modular multiplication without magnitude comparison Proceedings of the 6th National Conference on Information Security 1996 Taichung Taiwan 21\u201322."},{"key":"e_1_2_7_15_2","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0020-0190(99)00137-4","article-title":"Fast modular multiplication algorithm for calculating the product ab modulo n","volume":"72","author":"Chen C.-Y.","year":"1999","journal-title":"Information Processing Letters"},{"key":"e_1_2_7_16_2","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1109\/TC.1983.1676262","article-title":"A computer algorithm for calculation the product ab modulo m","volume":"32","author":"Blakley G. R.","year":"1983","journal-title":"IEEE Transactions on Computers"},{"key":"e_1_2_7_17_2","doi-asserted-by":"crossref","unstructured":"OrupH.andKornerupP. A high-radix hardware algorithm for calculating the exponentialmemodulon 576 Proceedings of the 10th IEEE Symposium on Computer Arithmetic June 1991 51\u201357.","DOI":"10.1109\/ARITH.1991.145533"},{"key":"e_1_2_7_18_2","doi-asserted-by":"crossref","unstructured":"WalterC. D. Faster multiplication by operand scaling 576 Proceedings of the Advancesin Cryptology (Crypto \u203291) 1991 313\u2013323 Lecture Notes in Computer Science.","DOI":"10.1007\/3-540-46766-1_26"},{"key":"e_1_2_7_19_2","unstructured":"ModuguR.andChoiM. A fast low-power modulo 2n+ 1 multiplier design Proceedings of the IEEE International Instrumentation and Measurement Technology Conference (I2MTC \u203209) 2009."},{"key":"e_1_2_7_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1958.5222579"},{"key":"e_1_2_7_21_2","doi-asserted-by":"publisher","DOI":"10.1049\/el:19940969"},{"key":"e_1_2_7_22_2","unstructured":"DhemJ.-F. Design of an efficient public-key cryptographic library forRISC based smart cards Ph.D. thesis May1998 Universit\u00e9 Catholique de Louvain."},{"key":"e_1_2_7_23_2","doi-asserted-by":"crossref","unstructured":"ShandM.andVuilleminJ. Fast Implementations of RSA cryptography Proceedings of the 11th IEEE Symposium on Computer Arithmetic July 1993 252\u2013259 2-s2.0-0027188810.","DOI":"10.1109\/ARITH.1993.378085"},{"key":"e_1_2_7_24_2","doi-asserted-by":"crossref","unstructured":"OrupH. Simplifying quotient determination in high-radix modular multiplication Proceedings of the 12th IEEE Symposium on Computer Arithmetic July 1995 193\u2013199 2-s2.0-0029226591.","DOI":"10.1109\/ARITH.1995.465359"},{"key":"e_1_2_7_25_2","doi-asserted-by":"crossref","unstructured":"BosselaersA. GovaertsR. andVandewalleJ. Comparisons of three modular reduction functions 773 Proceedings of the Advancesin Cryptology (Crypto \u203293) 1993 175\u2013186 Lecture Notes in Computer Science.","DOI":"10.1007\/3-540-48329-2_16"},{"key":"e_1_2_7_26_2","unstructured":"BosselaersA. GovaertsR. andVandewalleJ. A fast and flexible software library for large integer arithmetic Proceedings of the 15th Symposiumon Information Theory in the Benelux Louvain-La-Neuve(B) 1994 82\u201389."},{"key":"e_1_2_7_27_2","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/511120.511123","article-title":"Architectural tradeoff in implementing RSA processors","volume":"30","author":"Chang F. C.","year":"2002","journal-title":"ACM SIGARCH Computer Architecture News"},{"key":"e_1_2_7_28_2","doi-asserted-by":"crossref","unstructured":"WalterC. D. KocC.-K.andPaarC. Montgomery\u2019s multiplication technique: how to make it smaller and faster 1717 Proceedings of the 1st International Workshop on Cryptographic Hardware and Embedded Systems (CHES \u203299) August 1999 Worcester Ma USA 80\u201393 Lecture Notes in Computer Science.","DOI":"10.1007\/3-540-48059-5_9"},{"key":"e_1_2_7_29_2","doi-asserted-by":"publisher","DOI":"10.1049\/el:19941383"},{"key":"e_1_2_7_30_2","unstructured":"LimC. H. HwangH. S. andLeeP. J. Fast modular reduction with precomputation Proceedings of the Japan-Korea Joint Workshop on Information Security and Cryptology (JW-ISC \u203297) October 1997 65\u201379."},{"key":"e_1_2_7_31_2","doi-asserted-by":"publisher","DOI":"10.1049\/ip\u2010cdt:20040791"},{"key":"e_1_2_7_32_2","doi-asserted-by":"crossref","unstructured":"NozakiH. MotoyamaM. ShimboA. andKawamuraS. Implementation of RSA algorithm based on RNS montgomery multiplication Proceedings of the Cryptographic Hardware and Embedded Systems (CHES \u203201) September 2001 364\u2013376.","DOI":"10.1007\/3-540-44709-1_30"},{"key":"e_1_2_7_33_2","unstructured":"KongY.andPhillipsB. Montgomery modular multiplier 2005 The University of Adelaide Adelaide Australia."}],"container-title":["Journal of Electrical and Computer Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/jece\/2010\/657076.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/jece\/2010\/657076.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/2010\/657076","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T09:35:20Z","timestamp":1740735320000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/2010\/657076"}},"subtitle":[],"editor":[{"given":"Yong-Bin","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1155\/2010\/657076"],"URL":"https:\/\/doi.org\/10.1155\/2010\/657076","archive":["Portico"],"relation":{},"ISSN":["2090-0147","2090-0155"],"issn-type":[{"type":"print","value":"2090-0147"},{"type":"electronic","value":"2090-0155"}],"subject":[],"published":{"date-parts":[[2010,1]]},"assertion":[{"value":"2010-03-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-09-15","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-11-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"657076"}}