The Canonical Lift of an Ordinary Elliptic Curve over a Finite Field and its Point Counting, by Takakazu Satoh

Preprint #0223 is an updated version of this preprint. We develop a probabilistic algorithm for the point counting of an elliptic curve E defined over the finite field with pN elements provided that p is small enough and that j(E) does not belong to the finite field with p2 elements. For simplicity, we are concerned to the case p>3. The so-called Schoof-Elkies-Atkin algorithm requires O((N log p)4 + \epsilon). Our algorithm is O(N3 + \epsilon) where O-constant depends (badly) on p. Our idea is totally different from SEA algorithm. We lift E to its canonical lift and compute the trace of Verschiebung (i.e. the dual of the Frobenius morphism) directly from characteristic zero information.

Takakazu Satoh <tsatoh@rimath.saitama-u.ac.jp>