18. August 2014

The number of multi-base representations of an integer


In a multi-base representation of an integer (in contrast to, for example, the binary or decimal representation) the base (or radix) is replaced by products of powers of single bases. The resulting numeral system is usually redundant, which means that each integer can have multiple different digit expansions.

The motivation studying such expansions comes from cryptography. For fast arithmetic (e.g., algorithms for exponentiation in a finite group or the scalar multiplication on elliptic curves), the right choice of the numeral system is an important aspect.

This talks will focus on the following enumerative combinatorics problem: What is the number of multi-base representations of a positive integer n? We provide a general asymptotic formula for this number. Moreover, we analyze the sum of digits and the Hamming weight of a random representation. The proofs of all these results are based on a saddle-point analysis of the associated generating functions.

  • This talk was given at Algorithmic and Enumerative Combinatorics Summer School 2014, Hagenberg (Austria), August 18–22, 2014.
  • Downloads:
  • categories: math, talk