Let p be a prime; using modular polynomial \(\Phi _p\) , Satoh (J Ramanujan Math Soc 15(4):247–270, 2000), Vercauteren (Computing zeta functions of curves over finite fields. PhD Thesis, Katholieke Universiteit Leuven, 2003), Gaudry (Algorithmes de comptage de points d’une courbe définie sur un corps fini, 2004, http://www.loria.fr/gaudry/publis/pano.pdf) developed several algorithms to compute the canonical lift of an ordinary elliptic curve E over \(\mathbb {F}_{p^n}\) with j-invariant not in \(\mathbb {F}_{p^2}\) . When p is constant, the best variant has complexity \(\tilde{O}(n m)\) bit operations to lift E to p-adic precision m. As an application, lifting E to precision \(m=O(n)\) allows to recover its cardinality in time \(\tilde{O}(n^2)\) . However, taking p into account the complexity is \(\tilde{O}(p^2 n m)\) , so Satoh’s algorithm can only be applied to small p. We propose in this paper two variants of these algorithms, which do not rely on the modular polynomial, for computing the canonical lift of an ordinary curve. Our new method yields a complexity of \(\tilde{O}(p n m)\) to lift at precision m, and even \(\tilde{O}(p^{0.5} nm)\) when we are provided a rational point of p-torsion on the curve. This allows us to extend Satoh’s point counting algorithm to larger p.
