Journal of Symbolic Computation vol:44 issue:9 pages:1255-1267
MEGA edition:2007 location:Strobl date:24-30 June 2007
Let E be a nonsupersingular elliptic curve over the finite field with p^n elements. We present a deterministic algorithm that computes the zeta function and hence the number of points of such a curve E in time quasi-quadratic in n. An older algorithm having the same time complexity uses the canonical lift of E, whereas our algorithm uses rigid cohomology combined with a deformation approach. An implementation in small odd characteristic turns Out to give very good results.