Preda Mihailescu
Elliptic Curve Gauss Sums and Counting Points.
Preprint series: Mathematica Gottingensis
Abstract: Recently, Bostan, Morain, Salvy and Schost gave a very fast algorithm
for computing isogenies. If $\id{E}$ is an elliptic curve over a
finite field $\F_p$, this algorithm can yield eigenpolynomials -- and
thus eigenpoints -- of the Frobenius in some torsion set
$\id{E}[\ell]$, if such eigenpoints exist. In the context of the SEA
method \cite{Sch} for counting points on elliptic curves, this brings
the cost for computation of the corresponding eigenvalue -- a discrete
logarithm -- together with the computations of zeroes of the modular
equation to the foreground.

We show that the discrete logarithm can be further improved, by
evaluating the Frobenius in extensions of minimal degree over $\F_p$;
these extensions are generated by what we call {\em Elliptic curve
Gauss sums}, by analogy to the cyclotomic curves. In fact the
algorithm we present here inherits its shape from a fast algorithm for
factoring cyclotomic polynomials over finite fields, which was
proposed in the thesis \cite{Mi}.
Keywords: Elliptic curve Gauss sums