Elliptic Gauss sums and applications to point counting (Q979143)

Let \({\mathbb K}\) be a (finite) field and let \(f(X)\in {\mathbb K}[X]\) be a polynomial of degree \(n\). Assume that there exists a polynomial \(C(X)\in {\mathbb K}[X]\), whose \(m\)th iterate \(C\circ C\circ\ldots \circ C\) is denoted by \(C^{(m)}(X)\), such that the following properties are verified: A. \(f(C(X))\equiv 0\bmod f(X)\). B. \(C^{(n)}(X)-X\equiv 0\bmod f(X)\) and \((C^{(m)}(X)-X,f(X))=1\) for \(m<n\). Then the \({\mathbb K}\)-algebra \({\mathbf A}={\mathbb K}[X]/(f(X))\) is called a polynomial cyclic algebra with cyclicity polynomial \(C(X)\), and \(f(X)\) is called a cyclic polynomial.The authors study the structure of these algebras. Gauss and Jacobi sums over such algebras are applied for improving current algorithms for counting the number of points of elliptic curves over finite fields.