Efficient point multiplication for elliptic curves over special optimal extension fields (Q2764243)

\textit{R. P. Gallant, R. J. Lambert} and \textit{S. A. Vanstone} [Faster point multiplication on elliptic curves with efficient endomorphisms (2001; Zbl 1002.94022)] have developed an algorithm for fast multiplication of points on elliptic curves over finite fields, based on the existence of efficient endomorphisms. Basically, the idea for computing \(kP\) for a certain point \(P\) of order \(n\) and a certain integer \(0<k<n\) is to look for expansions: \(kP=k_0P+k_1\psi(P)\), where \(k_0,k_1\) are integers of size approximately \(\sqrt n\) and \(\psi\) is an endomorphism of the elliptic curve whose evaluation is sufficiently fast. This expression can then be evaluated with parallel point multiplication techniques. NEWLINENEWLINENEWLINEIn the paper under review these ideas are generalized to expansions involving higher powers of \(\psi\). To this end some variants of simultaneous multiple point multiplication algorithms are worked out. The suitable scenario for this generalization to be of practical use are the optimal extension fields introduced by Bailey and Paar, which are fields generated by irreducible polynomials of the form \(X^r-m\) over a prime field \(\mathbb{F}_p\), with \(p=2^t-s\), \(t=31,32\) and \(s\) small. The paper presents computations for some elliptic curves defined over \(\mathbb{F}_p\) such that the group of points \(E(\mathbb{F}_{p^7})\) has cryptographic relevance and the Frobenius endomorphism leads to expansions of length 7 where the method works efficiently. Due to the efficient implementation of the field arithmetic for optimal extension fields, this multiplication algorithm makes these curves good candidates for fast software implementation of elliptic curve cryptography on 32-bit computers.NEWLINENEWLINEFor the entire collection see [Zbl 0976.00054].