An improved algorithm for arithmetic on a family of elliptic curves (Q4364563)

Applications in cryptography on elliptic curves over finite fields are based on integer multiples \(nP\) of a point \(P\) on the curve. The author discusses efficiency improvements of this scalar multiplication. These speedups originate from the following facts. i) One can choose the elliptic curve and the field of constants over which the curve is defined in an appropriate way. ii) Subtraction and addition on elliptic curves are equally efficient. iii) Elliptic curves over finite fields have endomorphisms which are not scalar multiplications. A very important one is the Frobenius endomorphism. The author considers the elliptic curves in characteristic 2 given by \[ y^2+ y= x+ \tfrac 1x+a \] with \(a=0\), \(1\in \mathbb{F}_2\). The representation of \(n\) using ii) and iii) combined with precomputation and storage yields a considerable efficiency improvement of scalar multiplication on the above-mentioned elliptic curves. For the entire collection see [Zbl 0870.00047].