Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

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
DOI: https://doi.org/10.1090/mcom/3227
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?)


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
Email: math@danielkrenn.at, daniel.krenn@aau.at

Volker Ziegler
Affiliation: Fachbereich für Mathematik, University of Salzburg, Hellbrunnerstrasse 34, A-5020 Salzburg, Austria
Email: volker.ziegler@sbg.ac.at

DOI: https://doi.org/10.1090/mcom/3227
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