Elliptic curve cryptography relies on the fact that multiples of a point can be computed easily, whereas the inverse problem (discrete logarithm on elliptic curves) seems to be hard. Since subtraction on elliptic curves is as cheap as addition, scalar multiplication can be done using a double, add and subtract algorithm using a binary expansion with digits . On special Koblitz curves, the doublings can be avoided by using the Frobenius endomorphism. In that case, the digit expansions have to be made with respect to a quadratic algebraic integer base. Optimal expansions as well as their analysis will be discussed.