Optimal and Non-Optimal Digit Expansions in Cryptography

Daniel Krenn^*

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?

Mathematics Subject Classification: 11A63 94A60 90C27

Keywords: optimal expansion, non-adjacent form, minimal weight, elliptic curve scalar multiplication, cryptography

Contributed Talks