11. September 2013

Optimal and non-optimal digit expansions in cryptography


In (hyper-)elliptic curve cryptography one has to perform arithmetic in the point group of the curve. Building multiples nP of a point P is the main operation, and clearly one goal is to make it as efficient as possible. By choosing a ``good'' numeral system to express the integer n, the mentioned operation can be sped up. In the talk we will see such numeral systems and see why they are a good choice. In particular, we study the following question: When are non-adjacent form digit expansions optimal in the sense that they minimize the number of non-zero digits?