Minimality and other properties of the width- nonadjacent form |
| |
Authors: | James A. Muir Douglas R. Stinson. |
| |
Affiliation: | Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 ; School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 |
| |
Abstract: | Let be an integer and let be the set of integers that includes zero and the odd integers with absolute value less than . Every integer can be represented as a finite sum of the form , with , such that of any consecutive 's at most one is nonzero. Such representations are called width- nonadjacent forms ( -NAFs). When these representations use the digits and coincide with the well-known nonadjacent forms. Width- nonadjacent forms are useful in efficiently implementing elliptic curve arithmetic for cryptographic applications. We provide some new results on the -NAF. We show that -NAFs have a minimal number of nonzero digits and we also give a new characterization of the -NAF in terms of a (right-to-left) lexicographical ordering. We also generalize a result on -NAFs and show that any base 2 representation of an integer, with digits in , that has a minimal number of nonzero digits is at most one digit longer than its binary representation. |
| |
Keywords: | Efficient representations minimal weight elliptic curve arithmetic |
|
| 点击此处可从《Mathematics of Computation》浏览原始摘要信息 |
|
点击此处可从《Mathematics of Computation》下载全文 |
|