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)

 

Remarks on the Schoof-Elkies-Atkin algorithm


Author: L. Dewaghe
Journal: Math. Comp. 67 (1998), 1247-1252
MSC (1991): Primary 14H52, 14K02, 11Y16
MathSciNet review: 1468941
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Schoof's algorithm computes the number $m$ of points on an elliptic curve $E$ defined over a finite field ${\Bbb F}_q$. Schoof determines $m$ modulo small primes $\ell$ using the characteristic equation of the Frobenius of $E$ and polynomials of degree $O(\ell^2)$. With the works of Elkies and Atkin, we have just to compute, when $\ell$ is a ``good" prime, an eigenvalue of the Frobenius using polynomials of degree $O(\ell)$. In this article, we compute the complexity of Müller's algorithm, which is the best known method for determining one eigenvalue and we improve the final step in some cases. Finally, when $\ell$ is ``bad", we describe how to have polynomials of small degree and how to perform computations, in Schoof's algorithm, on $x$-values only.


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


Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 14H52, 14K02, 11Y16

Retrieve articles in all journals with MSC (1991): 14H52, 14K02, 11Y16


Additional Information

L. Dewaghe
Affiliation: Université de Lille I, UFR de Mathématiques, 59655 Villeneuve d’Ascq cedex, France
Email: dewaghe@gat.univ-lille1.fr

DOI: http://dx.doi.org/10.1090/S0025-5718-98-00962-4
PII: S 0025-5718(98)00962-4
Keywords: Elliptic curves, finite fields, Schoof algorithm, division polynomials, computational number theory
Received by editor(s): May 11, 1996
Received by editor(s) in revised form: October 2, 1996, and February 19, 1997
Article copyright: © Copyright 1998 American Mathematical Society