Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

Author: René Schoof
Journal: Math. Comp. 44 (1985), 483-494
MSC: Primary 11Y16; Secondary 11G20, 14G15
MathSciNet review: 777280
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y16, 11G20, 14G15

Retrieve articles in all journals with MSC: 11Y16, 11G20, 14G15

Additional Information

Keywords: Elliptic curves, finite fields, factorization, polynomials, computational number theory
Article copyright: © Copyright 1985 American Mathematical Society