An improved algorithm for arithmetic on a family of elliptic curves. (English) Zbl 1032.11062

Kaliski, Burton S. jun. (ed.), Advances in Cryptology - CRYPTO ’97. 17th annual international cryptology conference. Santa Barbara, CA, USA. August 17-21, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1294, 357-371 (1997).
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].


11Y16 Number-theoretic algorithms; complexity
14Q05 Computational aspects of algebraic curves
11G20 Curves over finite and local fields
94A60 Cryptography