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

  • 1. A. O. L. Atkin, The number of points on an elliptic curve modulo a prime (I). Draft, 1988.
  • 2. A. O. L. Atkin, The number of points on an elliptic curve modulo a prime (II). Draft, 1992.
  • 3. R. C. Bose, S. Chowla, C. R. Rao, On the integral order (mod p) of quadratics $x^2+ax+b$, with applications to the construction of minimum functions over $GF(p^2)$, and to some number theory results, Bull. Calcutta Math. Soc., 36 (1944), pp. 153-174. MR 6:256b
  • 4. R. P. Brent, H. T. Kung, Fast algorithms for manipulating formal power series, J. Assoc. Comput. Mach., 25, 581-595, 1978. MR 58:25090
  • 5. J.-M. Couveignes, F. Morain, Schoof's algorithm and isogeny cycles, In L. Adleman and M.-D. Huang, editors, ANTS-I, volume 877 of Lecture Notes in Comput. Sci., pages 43-58. Springer-Verlag, 1994. MR 95m:11147
  • 6. J.-M. Couveignes, L. Dewaghe, F. Morain, Isogeny cycles and Schoof's algorithm, Preprint 1995.
  • 7. J.-M. Couveignes, Quelques calculs en théorie des nombres, Thèse, Université de Bordeaux I, July 1994.
  • 8. L. Dewaghe, Nombre de points d'une courbe elliptique sur un corps fini, Thèse, Université de Lille I, 1996.
  • 9. R. J. McEliece, Finite fields for computer scientists and engineers, Kluwer Boston 1987. MR 88h:11091
  • 10. N. D. Elkies, Explicit Isogenies, Draft, 1991.
  • 11. D. E. Knuth, The Art of Computer Programming : Seminumerical Algorithms, Addison-Wesley, 1981. MR 83i:68003
  • 12. R. Lercier and F. Morain, Counting the number of points on elliptic curves over finite fields:
    strategies and performances, In L. C. Guillou and J.-J. Quisquater, editors, Advances in cryptology - EUROCRYPT'95, number 921 of Lecture Notes in Comput. Sci. pp. 79-94, 1995. MR 96h:11060
  • 13. R. Lercier, F. Morain, Counting points on elliptic curves over ${\Bbb F}_{p^n}$ using Couveignes's algorithm. Research Report LIX/RR/95/09, Ecole polytechnique - LIX, September 1995.
  • 14. A. Menezes, S. Vanstone and R. Zuccherato, Counting points on elliptic curves over ${\Bbb F}_{2^m}$, Math. Comp. 60, 407-420, 1993. MR 93f:11098
  • 15. F. Morain, Calcul du nombre de points sur une courbe elliptique dans un corps fini : aspects algorithmiques, J. Théor. Nombres Bordeaux 7 (1995), 255-282. MR 97i:11069
  • 16. V. Müller, Looking for the eigenvalue in Schoof's algorithm, In preparation, October 1994.
  • 17. R. Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44, 483-494, 1985. MR 86e:11122
  • 18. R. Schoof, Counting points on elliptic curves over finite fields, J. Théor. Nombres Bordeaux 7 (1995), 219-254. MR 97i:11070
  • 19. V. Shoup, A new polynomial factorization algorithm and its implementation, J Symbolic Comput. (1995) Vol 20, 363-397. MR 97d:12011
  • 20. J. H. Silverman, The arithmetic of elliptic curves, vol. 106 of Graduate Texts in Mathematics, Springer, 1986. MR 87g:11070

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

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

American Mathematical Society