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>