Satoh, Takakazu The canonical lift of an ordinary elliptic curve over a finite field and its point counting. (English) Zbl 1009.11051 J. Ramanujan Math. Soc. 15, No. 4, 247-270 (2000). Summary: This paper is concerned with the problem of counting the number of points on an elliptic curve over a field \(\mathbb F_{p^N}\) in the case where \(p\) is a small prime and \(N\) is a large integer. For simplicity we restrict to the case of \(p\geq 5\). Our idea is different from the method of Schoof, Elkies and Atkin. We lift \(E\) to its canonical lift and compute the trace of Verschiebung (i.e. the dual of the Frobenius morphism) directly in characteristic zero. Define \(\mu>0\) so that the complexity of multiplication of two \(n\)-bit objects is \(O(n^\mu)\) bit operations. The method of Elkies with Couveignes’ isogeny finding algorithm runs in heuristically \(O((N\log p)^{2\mu+2})\) bit operations while our algorithm runs in \(O(N^{2\mu+1})\) bit operations where the \(O\)-constant depends (badly) on \(p\). Cited in 6 ReviewsCited in 32 Documents MSC: 11G20 Curves over finite and local fields 11Y16 Number-theoretic algorithms; complexity 14G50 Applications to coding theory and cryptography of arithmetic geometry Keywords:finite field; number of points; elliptic curve PDF BibTeX XML Cite \textit{T. Satoh}, J. Ramanujan Math. Soc. 15, No. 4, 247--270 (2000; Zbl 1009.11051)