Minimality and other properties of the width nonadjacent form
Authors:
James A. Muir and Douglas R. Stinson
Journal:
Math. Comp. 75 (2006), 369384
MSC (2000):
Primary 94A60, 11T71, 14G50; Secondary 94B40
Published electronically:
July 12, 2005
MathSciNet review:
2176404
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
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 wellknown 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 (righttoleft) 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.
 1.
R. M. Avanzi.
A Note on the Sliding Window Integer Recoding and its LefttoRight Analogue, to appear in ``Workshop on Selected Areas in Cryptography  SAC 2004''.
 2.
I.
F. Blake, G.
Seroussi, and N.
P. Smart, Elliptic curves in cryptography, London Mathematical
Society Lecture Note Series, vol. 265, Cambridge University Press,
Cambridge, 2000. Reprint of the 1999 original. MR 1771549
(2001i:94048)
 3.
S. H. Chang and N. TsaoWu.
Distance and Structure of Cyclic Arithmetic Codes, in ``Proceedings of the Hawaii International Conference on System Sciences'' (1968), 463466.
 4.
H. Cohen.
Analysis of the Flexible Window Powering Algorithm, Preprint. Available from http://www.math.ubordeaux.fr/~cohen/window.dvi .
 5.
Henri
Cohen, Atsuko
Miyaji, and Takatoshi
Ono, Efficient elliptic curve exponentiation using mixed
coordinates, Advances in cryptology—ASIACRYPT’98
(Beijing), Lecture Notes in Comput. Sci., vol. 1514, Springer,
Berlin, 1998, pp. 51–65. MR
1726152, http://dx.doi.org/10.1007/3540496491_6
 6.
Daniel
M. Gordon, A survey of fast exponentiation methods, J.
Algorithms 27 (1998), no. 1, 129–146. MR 1613189
(99g:94014), http://dx.doi.org/10.1006/jagm.1997.0913
 7.
Darrel
Hankerson, Alfred
Menezes, and Scott
Vanstone, Guide to elliptic curve cryptography, Springer
Professional Computing, SpringerVerlag, New York, 2004. MR 2054891
(2005c:94049)
 8.
C. Heuberger, R. Katti, H. Prodinger and X. Ruan.
The Alternating Greedy Expansion and Applications to LefttoRight Algorithms in Cryptography, Preprint. Available from http://www.wits.ac.za/helmut/paperlst.htm .
 9.
Kenji
Koyama and Yukio
Tsuruoka, Speeding up elliptic cryptosystems by using a signed
binary window method, Advances in cryptology—CRYPTO ’92
(Santa Barbara, CA, 1992) Lecture Notes in Comput. Sci., vol. 740,
Springer, Berlin, 1993, pp. 345–357. MR
1287864, http://dx.doi.org/10.1007/3540480714_25
 10.
J.
H. van Lint, Introduction to coding theory, 3rd ed., Graduate
Texts in Mathematics, vol. 86, SpringerVerlag, Berlin, 1999. MR 1664228
(2000a:94001)
 11.
A. Miyaji, T. Ono and H. Cohen.
Efficient Elliptic Curve Exponentiation, in ``Information and Communication Security  ICICS '97'', Lecture Notes in Computer Science 1334 (1997), 282290.
 12.
Bodo
Möller, Improved techniques for fast exponentiation,
Information security and cryptology—ICISC 2002, Lecture Notes in
Comput. Sci., vol. 2587, Springer, Berlin, 2003,
pp. 298–312. MR
2080830, http://dx.doi.org/10.1007/3540365524_21
 13.
J. A. Muir and D. R. Stinson.
New Minimal Weight Representations for LefttoRight Window Methods, Technical Report CORR 200419, Centre for Applied Cryptographic Research. Available from http://www.cacr.math.uwaterloo.ca/techreports/2004.
 14.
K. Okeya, K. SchmidtSamoa, C. Spahn and T. Takagi.
Signed Binary Representations Revisited, in ``Advances in Cryptology  CRYPTO 2004'', Lecture Notes in Computer Science 3152 (2004), 123139.
 15.
George
W. Reitwiesner, Binary arithmetic, Advances in computers, Vol.
1, Academic Press, New York, 1960, pp. 231–308. MR 0122018
(22 #12745)
 16.
Jerome
A. Solinas, Efficient arithmetic on Koblitz curves, Des. Codes
Cryptogr. 19 (2000), no. 23, 195–249. Towards
a quartercentury of public key cryptography. MR 1759617
(2002k:14039), http://dx.doi.org/10.1023/A:1008306223194
 1.
 R. M. Avanzi.
A Note on the Sliding Window Integer Recoding and its LefttoRight Analogue, to appear in ``Workshop on Selected Areas in Cryptography  SAC 2004''.
 2.
 I. F. Blake, G. Seroussi and N. P. Smart.
Elliptic Curves in Cryptography, Cambridge University Press, 1999. MR 1771549 (2001i:94048)
 3.
 S. H. Chang and N. TsaoWu.
Distance and Structure of Cyclic Arithmetic Codes, in ``Proceedings of the Hawaii International Conference on System Sciences'' (1968), 463466.
 4.
 H. Cohen.
Analysis of the Flexible Window Powering Algorithm, Preprint. Available from http://www.math.ubordeaux.fr/~cohen/window.dvi .
 5.
 H. Cohen, A. Miyaji and T. Ono.
Efficient Elliptic Curve Exponentiation Using Mixed Coordinates, in ``Advances in Cryptology  ASIACRYPT '98'', Lecture Notes in Computer Science 1514 (1998), 5165. MR 1726152
 6.
 D. M. Gordon.
A Survey of Fast Exponentiation Methods, Journal of Algorithms 27 (1998), 129146. MR 1613189 (99g:94014)
 7.
 D. Hankerson, A. Menezes and S. Vanstone.
Guide to Elliptic Curve Cryptography, Springer, 2004. MR 2054891 (2005c:94049)
 8.
 C. Heuberger, R. Katti, H. Prodinger and X. Ruan.
The Alternating Greedy Expansion and Applications to LefttoRight Algorithms in Cryptography, Preprint. Available from http://www.wits.ac.za/helmut/paperlst.htm .
 9.
 K. Koyama and Y. Tsuruoka.
Speeding up Elliptic Cryptosystems by Using a Signed Binary Window Method, in ``Advances in Cryptology  CRYPTO '92'', Lecture Notes in Computer Science 740 (1993), 345357. MR 1287864
 10.
 J. H. van Lint,
Introduction to Coding Theory, 3rd edition, Springer, 1999. MR 1664228 (2000a:94001)
 11.
 A. Miyaji, T. Ono and H. Cohen.
Efficient Elliptic Curve Exponentiation, in ``Information and Communication Security  ICICS '97'', Lecture Notes in Computer Science 1334 (1997), 282290.
 12.
 B. Möller.
Improved Techniques for Fast Exponentiation, in ``Information Security and Cryptology  ICISC 2002'', Lecture Notes in Computer Science 2587 (2002), 298312. MR 2080830
 13.
 J. A. Muir and D. R. Stinson.
New Minimal Weight Representations for LefttoRight Window Methods, Technical Report CORR 200419, Centre for Applied Cryptographic Research. Available from http://www.cacr.math.uwaterloo.ca/techreports/2004.
 14.
 K. Okeya, K. SchmidtSamoa, C. Spahn and T. Takagi.
Signed Binary Representations Revisited, in ``Advances in Cryptology  CRYPTO 2004'', Lecture Notes in Computer Science 3152 (2004), 123139.
 15.
 G. W. Reitwiesner.
Binary Arithmetic, in Advances in Computers, Vol. 1, Academic Press, 1960, pp. 231308. MR 0122018 (22:12745)
 16.
 J. A. Solinas. Efficient arithmetic on Koblitz curves. Designs, Codes and Cryptography 19 (2000), 195249. MR 1759617 (2002k:14039)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2000):
94A60,
11T71,
14G50,
94B40
Retrieve articles in all journals
with MSC (2000):
94A60,
11T71,
14G50,
94B40
Additional Information
James A. Muir
Affiliation:
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1
Email:
jamuir@uwaterloo.ca
Douglas R. Stinson
Affiliation:
School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1
Email:
dstinson@uwaterloo.ca
DOI:
http://dx.doi.org/10.1090/S0025571805017692
PII:
S 00255718(05)017692
Keywords:
Efficient representations,
minimal weight,
elliptic curve arithmetic
Received by editor(s):
March 29, 2004
Received by editor(s) in revised form:
August 21, 2004
Published electronically:
July 12, 2005
Additional Notes:
The second author is supported by NSERC grant RGPIN 20311402.
Article copyright:
© Copyright 2005 American Mathematical Society
