Elliptic curves over finite fields and the computation of square roots mod $p$

Abstract:

In this paper we present a deterministic algorithm to compute the number of ${{\mathbf {F}}_q}$-points of an elliptic curve that is defined over a finite field ${{\mathbf {F}}_q}$ and which is given by a Weierstrass equation. The algorithm takes $O({\log ^9}q)$ elementary operations. As an application we give an algorithm to compute square roots $\bmod p$. For fixed $x \in {\mathbf {Z}}$, it takes $O({\log ^9}p)$ elementary operations to compute $\sqrt x \bmod p$.