The complexity of elliptic normal bases
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.
- Algorithms for exponentiation in finite fields
- Artin-Schreier extensions of normal bases
- Elliptic periods for finite fields
- Handbook of finite fields
- scientific article; zbMATH DE number 4154569 (Why is no real title available?)
- scientific article; zbMATH DE number 4023423 (Why is no real title available?)
- Low complexity normal bases
- Low Complexity Normal Elements over Finite Fields of Characteristic Two
- Normal bases from 1-dimensional algebraic groups
- Normal basis exhaustive search: 10 years later
- On finite field arithmetic in characteristic 2
- Optimal normal bases in \(GF(p^ n)\)
- Primitive Normal Bases for Finite Fields
- The Arithmetic of Elliptic Curves
- The equivariant complexity of multiplication in finite field extensions
- The trace of an optimal normal element and low complexity normal bases
This page was built for publication: The complexity of elliptic normal bases
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7008111)
