Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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

DOI: http://dx.doi.org/10.1090/S0025-5718-1985-0777280-6
PII: S 0025-5718(1985)0777280-6
Keywords: Elliptic curves, finite fields, factorization, polynomials, computational number theory
Article copyright: © Copyright 1985 American Mathematical Society