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

DOI10.1090/MCOM/3227MaRDI QIDQ4600710zbMATH OpenOpenAlexFDO

Authors Daniel Krenn, Volker Ziegler

Publication date 12 January 2018

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.01562

zbMATH Keywords

\(\tau\)-adic expansionsBaker-Davenport methodcontinued fractionselliptic curve cryptographyFrobenius endomorphismgeometry of numbersHamming weightKoblitz curveslinear forms in logarithmsredundant digit setsscalar multiplication

Mathematics Subject Classification ID

Radix representation; digital problems (11A63) Diophantine inequalities (11D75) Lattices and convex bodies (number-theoretic aspects) (11H06) Linear forms in logarithms; Baker's method (11J86) Computer solution of Diophantine equations (11Y50)

Abstract: This article deals with redundant digit expansions with an imaginary quadratic algebraic integer with trace $pm1$ as base and a minimal norm representatives digit set. For $wgeq2$ 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.

Recommendations

• Optimality of the width-w non-adjacent form: general characterisation and the case of imaginary quadratic bases
• Analysis of width-w non-adjacent forms to imaginary quadratic bases
• On Redundant τ-Adic Expansions and Non-adjacent Digit Sets
• Redundant \(\tau \)-adic expansions. I: Non-adjacent digit sets and their applications to scalar multiplication
• Nonadjacent Radix-τ Expansions of Integers in Euclidean Imaginary Quadratic Number Fields

Cites work

• A Survey of Fast Exponentiation Methods
• An explicit lower bound for a homogeneous rational linear form in logarithms of algebraic numbers. II
• An introduction to the geometry of numbers.
• Analysis of width-w non-adjacent forms to imaginary quadratic bases
• Classical theory of algebraic numbers
• Efficient arithmetic on Koblitz curves
• Existence and optimality of \(w\)-non-adjacent forms with an algebraic integer base
• scientific article; zbMATH DE number 176613 (Why is no real title available?)
• scientific article; zbMATH DE number 1302857 (Why is no real title available?)
• scientific article; zbMATH DE number 708816 (Why is no real title available?)
• scientific article; zbMATH DE number 1088246 (Why is no real title available?)
• scientific article; zbMATH DE number 1107696 (Why is no real title available?)
• scientific article; zbMATH DE number 3193698 (Why is no real title available?)
• Minimality and other properties of the width-𝑤 nonadjacent form
• Minimality of the Hamming Weight of the τ-NAF for Koblitz Curves and Improved Combination with Point Halving
• Minimum weight modified signed-digit representations and fast exponentiation
• Optimality of the width-w non-adjacent form: general characterisation and the case of imaginary quadratic bases
• Products of Prime Powers in Binary Recurrence Sequences Part I: The Hyperbolic Case, with an Application to the Generalized Ramanujan-Nagell Equation
• Redundant \(\tau \)-adic expansions. I: Non-adjacent digit sets and their applications to scalar multiplication
• Redundant \(\tau \)-adic expansions. II: Non-optimality and chaotic behaviour
• Scalar multiplication on Koblitz curves using the Frobenius endomorphism and its combination with point halving: extensions and mathematical analysis
• Selected Areas in Cryptography
• THE EQUATIONS 3x²−2 = y² AND 8x²−7 = z²

Cited in

(4)

• Analysis of width-w non-adjacent forms to imaginary quadratic bases
• Existence and optimality of \(w\)-non-adjacent forms with an algebraic integer base
• Some properties of ${\tau}$-adic expansions on hyperelliptic Koblitz curves
• Optimality of the width-w non-adjacent form: general characterisation and the case of imaginary quadratic bases

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Non-minimality of the width-\(w\) non-adjacent form in conjunction with trace one \(\tau\)-adic digit expansions and Koblitz curves in characteristic two

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4600710)