The canonical lift of an ordinary elliptic curve over a finite field and its point counting. (English) Zbl 1009.11051

Satoh, Takakazu

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\).

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