{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:36:08Z","timestamp":1760121368355,"version":"3.41.0"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2005,7,1]],"date-time":"2005-07-01T00:00:00Z","timestamp":1120176000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2005,7]]},"abstract":"<jats:p>Several cryptosystems rely on fast calculations of linear combinations in groups. One way to achieve this is to use joint signed binary digit expansions of small \u201cweight.\u201d We study two algorithms, one based on nonadjacent forms of the coefficients of the linear combination, the other based on a certain joint sparse form specifically adapted to this problem. Both methods are sped up using the sliding windows approach combined with precomputed lookup tables. We give explicit and asymptotic results for the number of group operations needed, assuming uniform distribution of the coefficients. Expected values, variances and a central limit theorem are proved using generating functions.Furthermore, we provide a new algorithm that calculates the digits of an optimal expansion of pairs of integers from left to right. This avoids storing the whole expansion, which is needed with the previously known right-to-left methods, and allows an online computation.<\/jats:p>","DOI":"10.1145\/1077464.1077473","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T16:00:45Z","timestamp":1131379245000},"page":"123-142","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Analysis of linear combination algorithms in cryptography"],"prefix":"10.1145","volume":"1","author":[{"given":"Peter J.","family":"Grabner","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Graz, Graz, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Clemens","family":"Heuberger","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Graz, Graz, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Helmut","family":"Prodinger","sequence":"additional","affiliation":[{"name":"University of the Witwatersrand, Johannesburg, South Africa"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00f6rg M.","family":"Thuswaldner","sequence":"additional","affiliation":[{"name":"Montanuniversit\u00e4t Leoben, Leoben, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-004-0229-5"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0913"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.02.012"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1077464.1077473"},{"key":"e_1_2_1_5_1","unstructured":"Graham R. L. Knuth D. E. and Patashnik O. 1994. Concrete Mathematics. A Foundation for Computer Science 2nd ed. Addison-Wesley Reading Mass.   Graham R. L. Knuth D. E. and Patashnik O. 1994. Concrete Mathematics. A Foundation for Computer Science 2nd ed. Addison-Wesley Reading Mass."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10998-004-0523-x"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1997.0179"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.863044"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008354106356"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1990240605311"},{"key":"e_1_2_1_11_1","first-page":"231","volume-title":"Advances in Computers","author":"Reitwiesner G. W.","unstructured":"Reitwiesner , G. W. 1960. Binary arithmetic . In Advances in Computers , Vol. 1 . Academic Press , New York , pp. 231 -- 308 . Reitwiesner, G. W. 1960. Binary arithmetic. In Advances in Computers, Vol. 1. Academic Press, New York, pp. 231--308."},{"key":"e_1_2_1_12_1","volume-title":"Tech. Rep. CORR 2001-41","author":"Solinas J. A.","year":"2001","unstructured":"Solinas , J. A. 2001 . Low-weight binary representations for pairs of integers . Tech. Rep. CORR 2001-41 . Univ. Waterloo (available at http:\/\/www.cacr.math.uwaterloo.ca\/techreports\/ 2001\/corr2001-41.ps). Solinas, J. A. 2001. Low-weight binary representations for pairs of integers. Tech. Rep. CORR 2001-41. Univ. Waterloo (available at http:\/\/www.cacr.math.uwaterloo.ca\/techreports\/2001\/corr2001-41.ps)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1004715619287"},{"key":"e_1_2_1_14_1","unstructured":"von zur Gathen J. and Gerhard J. 1999. Modern Computer Algebra Cambridge University Press New York.   von zur Gathen J. and Gerhard J. 1999. Modern Computer Algebra Cambridge University Press New York."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1077464.1077473","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1077464.1077473","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:23:51Z","timestamp":1750267431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1077464.1077473"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,7]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,7]]}},"alternative-id":["10.1145\/1077464.1077473"],"URL":"https:\/\/doi.org\/10.1145\/1077464.1077473","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2005,7]]},"assertion":[{"value":"2005-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}