**MSC:**- 11Y05

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}.