The complexity of elliptic normal bases (Q7008111)

This paper is about the complexity \(C(N)\) of elliptic normal bases \(N\) introduced by \textit{J.-M. Couveignes} and \textit{R. Lercier} [Finite Fields Appl. 15, No. 1, 1--22 (2009; Zbl 1216.11106)]. \(C(N)\) is defined as the total number of nonzero elements in the multiplication matrix of the normal bases. The authors study the complexity of normal bases from elliptic periods and give some bounds on this complexity using specific vectors. \N\NSection 1 is an introduction of normal basis, the methods to construct efficient normal bases, and a particular method using elliptic curves by Couveignes and Lercier. \N\NSection 2 contains some background material on elliptic curves and normal elements. Elliptic curves over a finite field \(K\) are defined in this section, as well as the \(L\)-rational points group associated with this curve, where \(L\) is a field extension of \(K\). A divisor \(D\) on an elliptic curve and an associated set of functions \(L(D)\), a finite dimensional vector space, are also defined. Couveignes and Lercier [loc. cit.] study the relations between elliptic functions in these linear spaces which result in nice multiplication formulas for their elliptic basis but its complexity was not analyzed. Normal bases are defined in this section and bounds of the complexity are provided in proposition 1. Although the analysis implies that most normal bases do not have low complexity, Theorem 1 provides some important results about the existence of elliptic normal bases with low complexity. \N\NThe main results of the paper are given in Section 3. In Lemma 1 a multiplication tensor for elliptic normal bases is defined. Using this, and Theorem 1, a bound of the complexity of the bases is given in Theorem 2, provided the existence of very specific vectors on which the complexity depends. This dependence is given by the weight of the selected vectors. In Section 4, three examples of elliptic normal bases are provided using Magma.