Isomorphisms between Artin-Schreier towers (Q4501043)

Let \(L_n\) be an extension of degree \(p^n\) of \(\mathbb{F}_q\) (a finite field with \(q=p^d\) elements). \(L_n\) is said to be an Artin-Schreier tower if there exists a chain of Artin-Schreier extensions: \[ L_n\supset L_{n-1}\supset\cdots \supset L_1\supset L_0= \mathbb{F}_q \] defined by \(L_{k+1}= L_k(x_{k+1})\) with \(x_{k+1}^p- x_{k+1}- a_k=0\), where \(a_k\in L_k\). The main result proved in this paper is: An isomorphism between two Artin-Schreier towers \(L_n\) and \(M_n\) of degree \(p^n\) over \(\mathbb{F}_q\) can be computed in \(O(n^6 p^n)\) operations in \(\mathbb{F}_q\) for fixed \(q\) and \(n\to \infty\). This result is relevant in the study of the complexity of computing the torsion points of abelian varieties, since the field of definition of \(p^n\)-torsion points of an abelian variety over \(\mathbb{F}_q\) is an Artin-Schreier tower.