Existence and Optimality of $w$-Non-adjacent Forms with an Algebraic Integer Base

Abstract

We consider digital expansions in lattices with endomorphisms acting as base. We focus on the $w$-non-adjacent form ($w$-NAF), where each block of $w$ consecutive digits contains at most one non-zero digit. We prove that for sufficiently large $w$ and an expanding endomorphism, there is a suitable digit set such that each lattice element has an expansion as a $w$-NAF. If the eigenvalues of the endomorphism are large enough and $w$ is sufficiently large, then the $w$-NAF is shown to minimise the weight among all possible expansions of the same lattice element using the same digit system.

References in corpus (2)

• Analysis of Width-$w$ Non-Adjacent Forms to Imaginary Quadratic Bases
• Optimality of the Width-$w$ Non-adjacent Form: General Characterisation and the Case of Imaginary Quadratic Bases

Cited by in corpus (1)

• Analysis of the Width-w Non-Adjacent Form in Conjunction with Hyperelliptic Curve Cryptography and with Lattices