{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T22:16:32Z","timestamp":1780956992847,"version":"3.54.1"},"reference-count":19,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2019,3,7]],"date-time":"2019-03-07T00:00:00Z","timestamp":1551916800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computers"],"abstract":"<jats:p>A minimal length addition chain for a positive integer m is a finite sequence of positive integers such that (1) the first and last elements in the sequence are 1 and m, respectively, (2) any element greater than 1 in the sequence is the addition of two earlier elements (not necessarily distinct), and (3) the length of the sequence is minimal. Generating the minimal length addition chain for m is challenging due to the running time, which increases with the size of m and particularly with the number of 1s in the binary representation of m. In this paper, we introduce a new parallel algorithm to find the minimal length addition chain for m. The experimental studies on multicore systems show that the running time of the proposed algorithm is faster than the sequential algorithm. Moreover, the maximum speedup obtained by the proposed algorithm is 2.5 times the best known sequential algorithm.<\/jats:p>","DOI":"10.3390\/computers8010023","type":"journal-article","created":{"date-parts":[[2019,3,8]],"date-time":"2019-03-08T04:58:35Z","timestamp":1552021115000},"page":"23","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["An Efficient Multicore Algorithm for Minimal Length Addition Chains"],"prefix":"10.3390","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9448-6168","authenticated-orcid":false,"given":"Hazem","family":"Bahig","sequence":"first","affiliation":[{"name":"College of Computer Science and Engineering, Hail University, Hail 81481, Kingdom of Saudi Arabia"},{"name":"Computer Science Division, Department of Mathematics, Faculty of Science, Ain Shams University, Cairo 11566, Egypt"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yasser","family":"Kotb","sequence":"additional","affiliation":[{"name":"Computer Science Division, Department of Mathematics, Faculty of Science, Ain Shams University, Cairo 11566, Egypt"},{"name":"College of Computer and Information Sciences, Information Systems Department, Imam Mohammad Ibn Saud Islamic University, Riyadh 11432, Kingdom of Saudi Arabia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2019,3,7]]},"reference":[{"key":"ref_1","unstructured":"Knuth, D.E. (1973). The Art of Computer Programming: Seminumerical Algorithms, Addison-Wesley."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1006\/jagm.1997.0913","article-title":"A Survey of fast exponentiation methods","volume":"27","author":"Gordon","year":"1998","journal-title":"J. Algorithms"},{"key":"ref_3","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":"Commun. ACM"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1049\/el:19950130","article-title":"Cryptanalysis of secure addition chain for SASC applications","volume":"31","author":"Yen","year":"1993","journal-title":"Electron. Lett."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/s00607-006-0170-6","article-title":"Improved generation of minimal addition chains","volume":"78","author":"Bahig","year":"2006","journal-title":"Computing"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/s00607-010-0122-z","article-title":"Star reduction among minimal length addition chains","volume":"91","author":"Bahig","year":"2011","journal-title":"Computing"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1007\/s11227-017-2129-0","article-title":"A fast optimal parallel algorithm for a short addition chain","volume":"74","author":"Bahig","year":"2018","journal-title":"J. Supercomput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"21","DOI":"10.5802\/jtnb.104","article-title":"Efficient computation of addition chains","volume":"6","author":"Bergeron","year":"1994","journal-title":"J. Th\u00e9orie Nr. Bordx."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/0196-6774(89)90036-9","article-title":"Addition chains using continued fractions","volume":"10","author":"Bergeron","year":"1989","journal-title":"J. Algorithms"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/s00607-010-0118-8","article-title":"Calculating optimal addition chains","volume":"91","author":"Clift","year":"2011","journal-title":"Computing"},{"key":"ref_11","first-page":"208","article-title":"Finding Optimal Addition Chains Using a Genetic Algorithm Approach","volume":"Volume 3801","year":"2005","journal-title":"Computational Intelligence and Security. CIS 2005. Lecture Notes in Computer Science"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/S0012-365X(99)00103-X","article-title":"Integers with a small number of minimal addition chains","volume":"205","author":"Flammenkamp","year":"1999","journal-title":"Discret. Math."},{"key":"ref_13","first-page":"41","article-title":"Jahresbericht: Deutsche Mathematiker Vereinigung","volume":"47","author":"Scholz","year":"1937","journal-title":"Aufgabe"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0012-365X(93)90303-B","article-title":"Addition chains\u2014An erratic sequence","volume":"122","author":"Thurber","year":"1993","journal-title":"Discret. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1247","DOI":"10.1137\/S0097539795295663","article-title":"Efficient generation of minimal length addition chains","volume":"28","author":"Thurber","year":"1999","journal-title":"SIAM J. Comput."},{"key":"ref_16","unstructured":"Bleichenbacher, D., and Flammenkamp, A. (2018, May 21). An Efficient Algorithm for Computing Shortest Addition Chains. Available online: http:\/\/www.homes.uni-bielefeld.de\/achim\/addition_chain.html."},{"key":"ref_17","unstructured":"Chin, Y., and Tsai, Y. (1985, January 20\u201322). Algorithms for finding the shortest addition chain. Proceedings of the National Computer Symposium, Kaoshiung, Taiwan."},{"key":"ref_18","first-page":"321","article-title":"Binary addition chain on EREW PRAM","volume":"Volume 7017","author":"Fathy","year":"2011","journal-title":"Proceedings of the International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP 2011)"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02242355","article-title":"Schnelle multiplikation GroBer Zahlen","volume":"7","author":"Schonhage","year":"1971","journal-title":"Computing"}],"container-title":["Computers"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-431X\/8\/1\/23\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:36:53Z","timestamp":1760186213000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-431X\/8\/1\/23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,7]]},"references-count":19,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2019,3]]}},"alternative-id":["computers8010023"],"URL":"https:\/\/doi.org\/10.3390\/computers8010023","relation":{},"ISSN":["2073-431X"],"issn-type":[{"value":"2073-431X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,7]]}}}