ACAC Seminar Abstract

ACAC Seminar Abstract

ACAC Seminars

ACAC Seminar Abstract

Minimal weight expansions in Pisot numeration systems

Speaker: Wolfgang Steiner
Date, Time: Fri, 28 Oct 2011 15:00

Sparse digital expansions of integers are used to speed up scalar multiplication in elliptic curves. It is well known that every integer $N$ can be written as a sum of at most about $(\log_2 |N|)/2$ signed powers of 2, using e.g. the so-called non-adjacent form. An even smaller amount of summations is needed when we want to write $N$ as a sum of signed Fibonacci numbers. For a digital expansion of the form $N = \sum_k d_k U_k$ with a base sequence $U_k$ and integer digits $d_k$, we call $\sum_k |d_k|$ the weight of the expansion. An expansion is said to have minimal weight if no other expansion of $N$ (with respect to the same base sequence) has smaller weight. We show that the set of expansions of minimal weight is recognised by a finite automaton when the base sequence satisfies a linear recurrence related to a Pisot number, such as the Fibonacci sequence. (A Pisot number is an algebraic integer larger than 1 with all its conjugates strictly inside the unit circle.) Since the redundancy of these representations can be used to resist against side channel attacks such as simple power analysis, we study the cardinality of the set of minimal weight expansions of a given number.

Back to the top of this page