# zbMATH — the first resource for mathematics

The canonical lift of an ordinary elliptic curve over a finite field and its point counting. (English) Zbl 1009.11051
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