{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T08:33:49Z","timestamp":1776846829104,"version":"3.51.2"},"reference-count":16,"publisher":"American Mathematical Society (AMS)","issue":"253","license":[{"start":{"date-parts":[[2006,7,12]],"date-time":"2006-07-12T00:00:00Z","timestamp":1152662400000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n Let\n \n \n \n \n w<\/mml:mi>\n \n \u2265\n \n <\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n w \\geq 2<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n be an integer and let\n \n \n \n \n D<\/mml:mi>\n w<\/mml:mi>\n <\/mml:msub>\n D_w<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n be the set of integers that includes zero and the odd integers with absolute value less than\n \n \n \n \n 2<\/mml:mn>\n \n w<\/mml:mi>\n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n 2^{w-1}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . Every integer\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n can be represented as a finite sum of the form\n \n \n \n \n n<\/mml:mi>\n =<\/mml:mo>\n \n \u2211\n \n <\/mml:mo>\n \n a<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n \n 2<\/mml:mn>\n i<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n n = \\sum a_i 2^i<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , with\n \n \n \n \n \n a<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n \n \u2208\n \n <\/mml:mo>\n \n D<\/mml:mi>\n w<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n a_i \\in D_w<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , such that of any\n \n \n \n w<\/mml:mi>\n w<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n consecutive\n \n \n \n \n a<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n a_i<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n \u2019s at most one is nonzero. Such representations are called\n \n width-\n \n \n \n w<\/mml:mi>\n w<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n nonadjacent forms\n <\/italic>\n (\n \n \n \n w<\/mml:mi>\n w<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -NAFs). When\n \n \n \n \n w<\/mml:mi>\n =<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n w=2<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n these representations use the digits\n \n \n \n \n {<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n \n \u00b1\n \n <\/mml:mo>\n 1<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n \\{0,\\pm 1\\}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and coincide with the well-known\n nonadjacent forms<\/italic>\n . Width-\n \n \n \n w<\/mml:mi>\n w<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n nonadjacent forms are useful in efficiently implementing elliptic curve arithmetic for cryptographic applications. We provide some new results on the\n \n \n \n w<\/mml:mi>\n w<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -NAF. We show that\n \n \n \n w<\/mml:mi>\n w<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -NAFs have a minimal number of nonzero digits and we also give a new characterization of the\n \n \n \n w<\/mml:mi>\n w<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -NAF in terms of a (right-to-left) lexicographical ordering. We also generalize a result on\n \n \n \n w<\/mml:mi>\n w<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -NAFs and show that any base 2 representation of an integer, with digits in\n \n \n \n \n D<\/mml:mi>\n w<\/mml:mi>\n <\/mml:msub>\n D_w<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , that has a minimal number of nonzero digits is at most one digit longer than its binary representation.\n <\/p>","DOI":"10.1090\/s0025-5718-05-01769-2","type":"journal-article","created":{"date-parts":[[2005,11,16]],"date-time":"2005-11-16T10:22:35Z","timestamp":1132136555000},"page":"369-384","source":"Crossref","is-referenced-by-count":25,"title":["Minimality and other properties of the width-\ud835\udc64 nonadjacent form"],"prefix":"10.1090","volume":"75","author":[{"given":"James","family":"Muir","sequence":"first","affiliation":[]},{"given":"Douglas","family":"Stinson","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2005,7,12]]},"reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"R. M. Avanzi. A Note on the Sliding Window Integer Recoding and its Left-to-Right Analogue, to appear in \u201cWorkshop on Selected Areas in Cryptography \u2013 SAC 2004\u201d.","DOI":"10.1007\/978-3-540-30564-4_9"},{"key":"2","series-title":"London Mathematical Society Lecture Note Series","isbn-type":"print","volume-title":"Elliptic curves in cryptography","volume":"265","author":"Blake, I. F.","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/0521653746"},{"key":"3","unstructured":"S. H. Chang and N. Tsao-Wu. Distance and Structure of Cyclic Arithmetic Codes, in \u201cProceedings of the Hawaii International Conference on System Sciences\u201d (1968), 463\u2013466."},{"key":"4","unstructured":"H. Cohen. Analysis of the Flexible Window Powering Algorithm, Preprint. Available from \\url{http:\/\/www.math.u-bordeaux.fr\/ cohen\/window.dvi}."},{"key":"5","isbn-type":"print","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/3-540-49649-1_6","article-title":"Efficient elliptic curve exponentiation using mixed coordinates","author":"Cohen, Henri","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/3540651098"},{"issue":"1","key":"6","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1006\/jagm.1997.0913","article-title":"A survey of fast exponentiation methods","volume":"27","author":"Gordon, Daniel M.","year":"1998","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"key":"7","series-title":"Springer Professional Computing","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1016\/s0012-365x(04)00102-5","volume-title":"Guide to elliptic curve cryptography","author":"Hankerson, Darrel","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/038795273X"},{"key":"8","unstructured":"C. Heuberger, R. Katti, H. Prodinger and X. Ruan. The Alternating Greedy Expansion and Applications to Left-to-Right Algorithms in Cryptography, Preprint. Available from \\url{http:\/\/www.wits.ac.za\/helmut\/paperlst.htm}."},{"key":"9","isbn-type":"print","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/3-540-48071-4_25","article-title":"Speeding up elliptic cryptosystems by using a signed binary window method","author":"Koyama, Kenji","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540573402"},{"key":"10","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58575-3","volume-title":"Introduction to coding theory","volume":"86","author":"van Lint, J. H.","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/3540641335","edition":"3"},{"key":"11","doi-asserted-by":"crossref","unstructured":"A. Miyaji, T. Ono and H. Cohen. Efficient Elliptic Curve Exponentiation, in \u201cInformation and Communication Security \u2013 ICICS \u201997\u201d, Lecture Notes in Computer Science 1334 (1997), 282\u2013290.","DOI":"10.1007\/BFb0028484"},{"key":"12","isbn-type":"print","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/3-540-36552-4_21","article-title":"Improved techniques for fast exponentiation","author":"M\u00f6ller, Bodo","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/3540007164"},{"key":"13","unstructured":"J. A. Muir and D. R. Stinson. New Minimal Weight Representations for Left-to-Right Window Methods, Technical Report CORR 2004-19, Centre for Applied Cryptographic Research. Available from http:\/\/www.cacr.math.uwaterloo.ca\/techreports\/2004."},{"key":"14","doi-asserted-by":"crossref","unstructured":"K. Okeya, K. Schmidt-Samoa, C. Spahn and T. Takagi. Signed Binary Representations Revisited, in \u201cAdvances in Cryptology \u2013 CRYPTO 2004\u201d, Lecture Notes in Computer Science 3152 (2004), 123\u2013139.","DOI":"10.1007\/978-3-540-28628-8_8"},{"key":"15","first-page":"231","article-title":"Binary arithmetic","author":"Reitwiesner, George W.","year":"1960"},{"issue":"2-3","key":"16","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1023\/A:1008306223194","article-title":"Efficient arithmetic on Koblitz curves","volume":"19","author":"Solinas, Jerome A.","year":"2000","journal-title":"Des. Codes Cryptogr.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-1022","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2006-75-253\/S0025-5718-05-01769-2\/S0025-5718-05-01769-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2006-75-253\/S0025-5718-05-01769-2\/S0025-5718-05-01769-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T14:33:57Z","timestamp":1776782037000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2006-75-253\/S0025-5718-05-01769-2\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,7,12]]},"references-count":16,"journal-issue":{"issue":"253","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["S0025-5718-05-01769-2"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-05-01769-2","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2005,7,12]]}}}