### 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 *p*^{N}
elements provided that *p* is small enough and that
*j*(*E*) does not belong to the finite field with
*p*^{2} 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*(*N*^{3 + \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>