Remote Access Mathematics of Computation
Green Open Access

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

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