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

$\displaystyle \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

$\displaystyle \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

$\displaystyle \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

Please send comments and corrections to Thomas Klausner.