Computing the ℓ-power torsion of an elliptic curve over a finite field

Miret, J.; Moreno, R.; Rio, A.; Valls, M.

doi:10.1090/S0025-5718-08-02201-1

Computing the $\ell$-power torsion of an elliptic curve over a finite field
HTML articles powered by AMS MathViewer

by J. Miret, R. Moreno, A. Rio and M. Valls PDF

Math. Comp. 78 (2009), 1767-1786 Request permission

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

Eric Bach and Jeffrey Shallit, Algorithmic number theory. Vol. 1, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996. Efficient algorithms. MR 1406794
I. F. Blake, G. Seroussi, and N. P. Smart, Elliptic curves in cryptography, London Mathematical Society Lecture Note Series, vol. 265, Cambridge University Press, Cambridge, 2000. Reprint of the 1999 original. MR 1771549
A. Bostan, F. Morain, B. Salvy, and É. Schost, Fast algorithms for computing isogenies between elliptic curves, Math. Comp. 77 (2008), no. 263, 1755–1778. MR 2398793, DOI 10.1090/S0025-5718-08-02066-8
L. Dewaghe, Isogénie entre courbes elliptiques, Util. Math. 55 (1999), 123–127 (French, with English and French summaries). MR 1685678
Mireille Fouquet and François Morain, Isogeny volcanoes and the SEA algorithm, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 276–291. MR 2041091, DOI 10.1007/3-540-45455-1_{2}3
Hiroshi Gunji, The Hasse invariant and $p$-division points of an elliptic curve, Arch. Math. (Basel) 27 (1976), no. 2, 148–158. MR 412198, DOI 10.1007/BF01224654
Dale Husemoller, Elliptic curves, Graduate Texts in Mathematics, vol. 111, Springer-Verlag, New York, 1987. With an appendix by Ruth Lawrence. MR 868861, DOI 10.1007/978-1-4757-5119-2
D. Kohel, Endomorphism rings of elliptic curves over finite fields, Ph.D. thesis, University of California at Berkeley, 1996.
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.
Magma Group, Handbook of Magma functions, J. Canon and W. Bosma, eds. Available from http://magma.maths.usyd.edu.au/.
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.
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), no. 249, 411–427. MR 2085900, DOI 10.1090/S0025-5718-04-01640-0
François Morain, Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques, J. Théor. Nombres Bordeaux 7 (1995), no. 1, 255–282 (French, with English and French summaries). Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). MR 1413579
E. Nart, Personal communication, May 2005.
Hans-Georg Rück, A note on elliptic curves over finite fields, Math. Comp. 49 (1987), no. 179, 301–304. MR 890272, DOI 10.1090/S0025-5718-1987-0890272-3
D. Sadornil, A note on factorisation of division polynomials Arxiv preprint arXiv:math/0606684v1 [math.NT], 2006.
René Schoof, Nonsingular plane cubic curves over finite fields, J. Combin. Theory Ser. A 46 (1987), no. 2, 183–211. MR 914657, DOI 10.1016/0097-3165(87)90003-3
Jean-Pierre Serre, Trees, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003. Translated from the French original by John Stillwell; Corrected 2nd printing of the 1980 English translation. MR 1954121
Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR 817210, DOI 10.1007/978-1-4757-1920-8
Hugues Verdure, Factorisation patterns of division polynomials, Proc. Japan Acad. Ser. A Math. Sci. 80 (2004), no. 5, 79–82. MR 2062806
Jacques Vélu, Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A-B 273 (1971), A238–A241 (French). MR 294345
J. F. Voloch, A note on elliptic curves over finite fields, Bull. Soc. Math. France 116 (1988), no. 4, 455–458 (1989) (English, with French summary). MR 1005390