# Znanstveni kolokviji

## Counting signed binary digit expansions of minimal Hamming weight

 Vrijeme: 2.11.200517:00 Predavaonica: 005 Predavač: Prof.dr. Clemens Heuberger, Graz University of Technology Naziv: Counting signed binary digit expansions of minimal Hamming weight Web stranica: Kliknite ovdje Opis: 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.

<< Povratak na popis kolokvija