Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 


Non-minimality of the width-$ w$ non-adjacent form in conjunction with trace one $ \tau$-adic digit expansions and Koblitz curves in characteristic two

Authors: Daniel Krenn and Volker Ziegler
Journal: Math. Comp. 87 (2018), 821-854
MSC (2010): Primary 11A63, 11Y50, 11D75
Published electronically: August 15, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This article deals with redundant digit expansions with an imaginary quadratic algebraic integer with trace $ \pm 1$ as base and a minimal norm representatives digit set. For $ w\geq 2$ it is shown that the width-$ w$ non-adjacent form is not an optimal expansion, meaning that it does not minimize the (Hamming) weight among all possible expansions with the same digit set. One main part of the proof uses tools from Diophantine analysis, namely the theory of linear forms in logarithms and the Baker-Davenport reduction method.

References [Enhancements On Off] (What's this?)

  • [1] Roberto Maria Avanzi, A note on the signed sliding window integer recoding and a left-to-right analogue, Selected areas in cryptography, Lecture Notes in Comput. Sci., vol. 3357, Springer, Berlin, 2005, pp. 130-143. MR 2180673,
  • [2] Roberto Maria Avanzi, Clemens Heuberger, and Helmut Prodinger, Minimality of the Hamming weight of the $ \tau $-NAF for Koblitz curves and improved combination with point halving, Selected areas in cryptography, Lecture Notes in Comput. Sci., vol. 3897, Springer, Berlin, 2006, pp. 332-344. MR 2241647,
  • [3] Roberto M. Avanzi, Clemens Heuberger, and Helmut Prodinger, Scalar multiplication on Koblitz curves using the Frobenius endomorphism and its combination with point halving: extensions and mathematical analysis, Algorithmica 46 (2006), no. 3-4, 249-270. MR 2291956,
  • [4] Roberto Avanzi, Clemens Heuberger, and Helmut Prodinger, Redundant $ \tau $-adic expansions I: non-adjacent digit sets and their applications to scalar multiplication, Des. Codes Cryptogr. 58 (2011), no. 2, 173-202. MR 2770310,
  • [5] A. Baker and H. Davenport, The equations $ 3x^{2}-2=y^{2}$ and $ 8x^{2}-7=z^{2}$, Quart. J. Math. Oxford Ser. (2) 20 (1969), 129-137. MR 0248079
  • [6] 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. MR 1771549
  • [7] J. W. S. Cassels, An Introduction to the Geometry of Numbers, Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen mit besonderer Berücksichtigung der Anwendungsgebiete, Bd. 99 Springer-Verlag, Berlin-Göttingen-Heidelberg, 1959. MR 0157947
  • [8] Daniel M. Gordon, A survey of fast exponentiation methods, J. Algorithms 27 (1998), no. 1, 129-146. MR 1613189,
  • [9] Clemens Heuberger, Redundant $ \tau $-adic expansions. II. Non-optimality and chaotic behaviour, Math. Comput. Sci. 3 (2010), no. 2, 141-157. MR 2608292,
  • [10] Clemens Heuberger and Daniel Krenn, Analysis of width-$ w$ non-adjacent forms to imaginary quadratic bases, J. Number Theory 133 (2013), no. 5, 1752-1808. MR 3007130,
  • [11] C. Heuberger and D. Krenn, Existence and optimality of $ w$-non-adjacent forms with an algebraic integer base, Acta Math. Hungar. 140 (2013), no. 1-2, 90-104. MR 3123865
  • [12] Clemens Heuberger and Daniel Krenn, Optimality of the width-$ w$ non-adjacent form: general characterisation and the case of imaginary quadratic bases, J. Théor. Nombres Bordeaux 25 (2013), no. 2, 353-386 (English, with English and French summaries). MR 3228312
  • [13] J. Jedwab and C. J. Mitchell, Minimum weight modified signed-digit representations and fast exponentiation, Electron. Lett. 25 (1989), 1171-1172.
  • [14] Neal Koblitz, CM-curves with good cryptographic properties, Advances in Cryptology--CRYPTO '91 (Santa Barbara, CA, 1991) Lecture Notes in Comput. Sci., vol. 576, Springer, Berlin, 1992, pp. 279-287. MR 1243654,
  • [15] Neal Koblitz, An elliptic curve implementation of the finite field digital signature algorithm, Advances in Cryptology--CRYPTO '98 (Santa Barbara, CA, 1998) Lecture Notes in Comput. Sci., vol. 1462, Springer, Berlin, 1998, pp. 327-337. MR 1670960,
  • [16] E. M. Matveev, An explicit lower bound for a homogeneous rational linear form in logarithms of algebraic numbers. II, Izv. Ross. Akad. Nauk Ser. Mat. 64 (2000), no. 6, 125-180; English transl., Izv. Math. 64 (2000), no. 6, 1217-1269. MR 1817252,
  • [17] Willi Meier and Othmar Staffelbach, Efficient multiplication on certain nonsupersingular elliptic curves, Advances in Cryptology--CRYPTO '92 (Santa Barbara, CA, 1992) Lecture Notes in Comput. Sci., vol. 740, Springer, Berlin, 1993, pp. 333-344. MR 1287863,
  • [18] A. Miyaji, T. Ono, and H. Cohen, Efficient elliptic curve exponentiation, Information and Communications Security. 1st International Conference, ICICS '97, Beijing, China, November 11-14, 1997. Proceedings (Yongfei Han, Tatsuaki Okamoto, and Sihan Qing, eds.), Lecture Notes in Comput. Sci., vol. 1334, Springer-Verlag, 1997, pp. 282-290.
  • [19] James A. Muir and Douglas R. Stinson, Minimality and other properties of the width-$ w$ nonadjacent form, Math. Comp. 75 (2006), no. 253, 369-384. MR 2176404,
  • [20] A. Pethő and B. M. M. de Weger, Products of prime powers in binary recurrence sequences. I. The hyperbolic case, with an application to the generalized Ramanujan-Nagell equation, Math. Comp. 47 (1986), no. 176, 713-727. MR 856715,
  • [21] B. Phillips and N. Burgess, Minimal weight digit set conversions, IEEE Trans. Comput. 53 (2004), 666-677.
  • [22] George W. Reitwiesner, Binary arithmetic, Advances in Computers, Vol. 1, Academic Press, New York, 1960, pp. 231-308. MR 0122018
  • [23] Paulo Ribenboim, Classical Theory of Algebraic Numbers, Universitext, Springer-Verlag, New York, 2001. MR 1821363
  • [24] The SageMath Developers, SageMath Mathematics Software (Version 7.0), 2016,
  • [25] J. A. Solinas, An improved algorithm for arithmetic on a family of elliptic curves, Advances in Cryptology -- CRYPTO '97. 17th Annual International Cryptology Conference, Santa Barbara, CA, August 17-21, 1997. Proceedings (B. S. Kaliski, ed.), Lecture Notes in Comput. Sci., vol. 1294, Springer, Berlin, 1997, pp. 357-371.
  • [26] Jerome A. Solinas, Efficient arithmetic on Koblitz curves, Des. Codes Cryptogr. 19 (2000), no. 2-3, 195-249. Towards a quarter-century of public key cryptography. MR 1759617,

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11A63, 11Y50, 11D75

Retrieve articles in all journals with MSC (2010): 11A63, 11Y50, 11D75

Additional Information

Daniel Krenn
Affiliation: Institut für Mathematik, Alpen-Adria-Universität Klagenfurt, Universitätsstraße 65–67, 9020 Klagenfurt am Wörthersee, Austria

Volker Ziegler
Affiliation: Fachbereich für Mathematik, University of Salzburg, Hellbrunnerstrasse 34, A-5020 Salzburg, Austria

Keywords: $\tau$-adic expansions, redundant digit sets, elliptic curve cryptography, Koblitz curves, Frobenius endomorphism, scalar multiplication, Hamming weight, linear forms in logarithms, geometry of numbers, Baker--Davenport method, continued fractions
Received by editor(s): April 6, 2016
Received by editor(s) in revised form: October 1, 2016
Published electronically: August 15, 2017
Additional Notes: The first author was supported by the Austrian Science Fund (FWF): I1136, by the Austrian Science Fund (FWF): P24644-N26, and by the Austrian Science Fund (FWF): W1230, Doctoral Program “Discrete Mathematics”.
The second author was supported by the Austrian Science Fund (FWF): P24801.
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society