Peter Grabner: Erdős measures and redundant digital expansion

Redundant binary representations of integers have been used in cryptography to speed up computations in Diffie-Hellman encryption schemes. Especially, in the case of elliptic curve cryptography, where addition and substraction are equally costly operations, representations of the form

$$\sum_{j=0}^J\varepsilon _j2^j\quad\varepsilon _j\in\{0,\pm1\}$$

are used. The redundance in the digit set is used to minimize the weight

$$\sum_{j=0}^J\vert\varepsilon _j\vert,$$

which represents the number of additions. This has been used by F. Morain and J. Olivos, who used the special case of the ``non-adjecent form'' ( $\forall j:\varepsilon _j\varepsilon _{j+1}=0$). We study the number $a(n)$ of representations of minimal weight. This turns out to be related to a measure $\nu$ on the interval $[-1,1]$, which has some similarities to the Erdos measures. We use a variant of the Jessen-Wintner theorem to show that this measure is singular continuous. Furthermore, this measure is used to show the asymptotic formula

$$\sum_{n<N}a(n)=N^{\log_2\alpha}F(\log_2N)(1+o(1)),$$

where $\alpha$ is the largest root of the polynomial $x^3-x^2-3x+1$ and $F$ is a continuous periodic function.

Back to the Index