We consider binary expansions of integers with digits ${0,pm1}$. The Hamming
weight of such an expansion is defined to be the number of nonzero digits. Expansions of minimal
Hamming weight are of particular interest in elliptic curve cryptography, where
the number of additions curve additions corresponds to the Hamming weight.
It is well-known (Reitwiesner 1960) that every integer has a unique
``Non-Adjacent-Form (NAF)'', i.e., an expansion where there are no adjacent
nonzeros. This NAF minimizes the Hamming weight amongst all signed binary
expansions of the same integer.
However, there are several optimal expansions of a given integer, and the NAF
ist just one of them. The main part of the talk will be devoted to determining
the average number of optimal expansions. In contrast to similar digital
counting problems, the result is emph{not} a leading term plus a fluctuation
in the second order term plus an error term, but the fluctuation already occurs
in the main term! Unfortunately, this also means that the usual methods do not
work. Instead, we constructed a suitable measure on the unit interval, studied
it and got our results.
Two dimensional analogues will also be discussed.
The talk is based on a joint papers with P.~Grabner and H.~Prodinger.
