Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Computing the $ \ell$-power torsion of an elliptic curve over a finite field


Authors: J. Miret, R. Moreno, A. Rio and M. Valls
Journal: Math. Comp. 78 (2009), 1767-1786
MSC (2000): Primary 11G20
DOI: https://doi.org/10.1090/S0025-5718-08-02201-1
Published electronically: October 29, 2008
MathSciNet review: 2501074
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The algorithm we develop outputs the order and the structure, including generators, of the $ \ell$-Sylow subgroup of the group of rational points of an elliptic curve defined over a finite field. To do this, we do not assume any knowledge of the group order. We are able to choose points in such a way that a linear number of successive $ \ell$-divisions leads to generators of the subgroup under consideration. After the computation of a couple of polynomials, each division step relies on finding rational roots of polynomials of degree $ \ell$. We specify in complete detail the case $ \ell=3$, when the complexity of each trisection is given by the computation of cubic roots in finite fields.


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

  • 1. E. BACH AND J. SHALLIT, Algorithmic Number Theory. Vol. 1: Efficient Algorithms, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996. MR 1406794 (97e:11157)
  • 2. I. BLAKE, G. SEROUSSI AND N. SMART, Elliptic curves in cryptography, London Math. Soc. Lecture Note Series, no. 265, Cambridge Unuversity Press, 1999. MR 1771549 (2001i:94048)
  • 3. A. BOSTAN, B. SALVY, F. MORAIN AND E. SCHOST, Fast algorithms for computing isogenies between elliptic curves, Math. Comp. 77 (2008), 1755-1778. MR 2398793
  • 4. L. DEWAGHE, Isogénie entre courbes elliptiques, Utilitas Mathematica (1999), no. 55, 123-127. MR 1685678 (2000b:14034)
  • 5. M. FOUQUET AND F. MORAIN, Isogeny volcanoes and the SEA algorithm, in ANTS-V, C. Fieker and D.R. Kohel, eds., Lecture Notes in Computer Science, Vol. 2369, Springer-Verlag, Berlin-Heidelberg-New York, 2002, pp. 276-291. MR 2041091 (2005c:11077)
  • 6. H. GUNJI, The Hasse invariant and $ p$-division points of an elliptic curve, Arch. Math., 27 (1976), pp. 148-158. MR 0412198 (54:325)
  • 7. D. HUSEM¨OLLER, Elliptic curves, Graduate Texts in Mathematics, Vol. 111, Springer-Verlag, Berlin-Heidelberg-New York, 1987. MR 868861 (88h:11039)
  • 8. D. KOHEL, Endomorphism rings of elliptic curves over finite fields, Ph.D. thesis, University of California at Berkeley, 1996.
  • 9. LIDIA-GROUP, LiDIA Manual: A library for computational number theory, Tech. Univ. Darmstadt, 2001. Available from ftp.informatik.tu-darmstadt.de/pub/TI/systems/LiDIA.
  • 10. MAGMA GROUP, Handbook of Magma functions, J. Canon and W. Bosma, eds. Available from http://magma.maths.usyd.edu.au/.
  • 11. J. MIRET, R. MORENO, AND A. RIO, Generalization of Vélu's formulae for isogenies, Proceedings of the Primeras Jornadas de Teorıa de Números (Vilanova i la Geltrú, 2005) Publ. Mat. (2007), Vol. Extra, pp. 147-163.
  • 12. J. MIRET, R. MORENO, A. RIO, AND M. VALLS, Determining the $ 2$-Sylow subgroup of an elliptic curve over a finite field, Math. Comp., 74 (2005), pp. 411-427. MR 2085900 (2005d:11090)
  • 13. F. MORAIN, Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques, Journal de Théorie des Nombres de Bordeaux (1995), no. 7, 255-282. MR 1413579 (97i:11069)
  • 14. E. NART, Personal communication, May 2005.
  • 15. H. G. RSUCK, A note on elliptic curves over finite fields, Math. Comp., 49 (1987), pp. 301-304. MR 890272 (88d:11058)
  • 16. D. SADORNIL, A note on factorisation of division polynomials Arxiv preprint arXiv:math/0606684v1 [math.NT], 2006.
  • 17. R. SCHOOF, Nonsingular plane cubic curves over finite fields, J. Combin. Theory Ser. A, 46 (1987), pp. 183-211. MR 914657 (88k:14013)
  • 18. J. P. SERRE, Trees, Springer Monographs in Mathematics, Springer-Verlag, Berlin-Heidelberg-New York, 2003. MR 1954121 (2003m:20032)
  • 19. J. H. SILVERMAN, The arithmetic of elliptic curves, Graduate Texts in Mathematics, Vol. 106, Springer-Verlag, Berlin-Heidelberg-New York, 1986. MR 817210 (87g:11070)
  • 20. H. VERDURE, Factorization patterns of division polynomials, Proc. Japan Acad. Ser. A Math. Sci., Vol. 80 (2004), pp. 79-82. Correction in [16]. MR 2062806 (2005b:11085)
  • 21. J. VŚELU, Isogénies entre courbes elliptiques, C. R. Math. Acad. Sci. Paris, Série A, vol. 273 (1971), pp. 238-241. MR 0294345 (45:3414)
  • 22. J. VOLOCH, A note on elliptic curves over finite fields, Bull. Soc. Math. France, 116 (1988), pp. 455-458. MR 1005390 (90f:14012)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11G20

Retrieve articles in all journals with MSC (2000): 11G20


Additional Information

J. Miret
Affiliation: Department de Matemàtica, Universitat de Lleida, Jaume II 69, 25001-Lleida, Spain
Email: miret@eps.udl.es

R. Moreno
Affiliation: Department de Matemàtica, Universitat de Lleida, Jaume II 69, 25001-Lleida, Spain
Email: ramiro@eps.udl.es

A. Rio
Affiliation: Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Jordi Girona 1-3. 08034-Barcelona, Spain
Email: ana.rio@upc.edu

M. Valls
Affiliation: Department de Matemàtica, Universitat de Lleida, Jaume II 69, 25001-Lleida, Spain
Email: magda@eps.udl.es

DOI: https://doi.org/10.1090/S0025-5718-08-02201-1
Received by editor(s): March 30, 2005
Received by editor(s) in revised form: May 28, 2008
Published electronically: October 29, 2008
Additional Notes: The first, second and fourth authors were supported in part by grant MTM2007-66842-C02-02.
The third author was supported in part by grants MTM2006-15038-C02-01 and 2005SGR 00443.
Article copyright: © Copyright 2008 American Mathematical Society

American Mathematical Society