Determining the $2$-Sylow subgroup of an elliptic curve over a finite field
HTML articles powered by AMS MathViewer
Abstract:
In this paper we describe an algorithm that outputs the order and the structure, including generators, of the $2$-Sylow subgroup of an elliptic curve over a finite field. To do this, we do not assume any knowledge of the group order. The results that lead to the design of this algorithm are of inductive type. Then a right choice of points allows us to reach the end within a linear number of successive halvings. The algorithm works with abscissas, so that halving of rational points in the elliptic curve becomes computing of square roots in the finite field. Efficient methods for this computation determine the efficiency of our algorithm.References
- Eric Bach and Jeffrey Shallit, Algorithmic number theory. Vol. 1, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996. Efficient algorithms. MR 1406794
- Jean-Marc Couveignes and François Morain, Schoof’s algorithm and isogeny cycles, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 43–58. MR 1322711, DOI 10.1007/3-540-58691-1_{4}2
- M. Fouquet, Anneau d’endomorphismes et cardinalité des courbes elliptiques: aspects algorithmiques, Ph.D. thesis, École Polytechnique, Paris, 2001.
- M. Fouquet and F. Morain, Isogeny volcanoes and the SEA algorithm, ANTS-V (C. Fieker and D.R. Kohel, eds.), LNCS, no. 2369, Springer-Verlag, 2002, pp. 276–291.
- 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
- Erik Woodward Knudsen, Elliptic scalar multiplication using point halving, Advances in cryptology—ASIACRYPT’99 (Singapore), Lecture Notes in Comput. Sci., vol. 1716, Springer, Berlin, 1999, pp. 135–149. MR 1773226, DOI 10.1007/978-3-540-48000-6_{1}2
- LiDIA-Group, LiDIA Manual: A library for computational number theory, Tech. Univ. Darmstad, 2001, Available from ftp.informatik.tu-darmstadt.de/pub/TI/systems/LiDIA.
- J.-F. Mestre, La méthode des graphes. Exemples et applications, Proceedings of the international conference on class numbers and fundamental units of algebraic number fields (Katata, 1986) Nagoya Univ., Nagoya, 1986, pp. 217–242 (French). MR 891898
- J. Miret, R. Moreno, D. Sadornil, J. Tena, and M. Valls, Isomorphism classes of elliptic curves with even order over a finite field, Int. Math. J. 2 (2002), no. 9, 931–942. MR 1919682
- 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
- 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
- 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
- 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
Bibliographic Information
- J. Miret
- Affiliation: Department de Matemàtica, Universitat de Lleida, Jaume II 69, 25001-Lleida, Spain
- Email: miret@eup.udl.es
- R. Moreno
- Affiliation: Department de Matemàtica, Universitat de Lleida, Jaume II 69, 25001-Lleida, Spain
- Email: ramiro@eup.udl.es
- A. Rio
- Affiliation: Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028-Barcelona, Spain
- MR Author ID: 364632
- Email: ana.rio@upc.es
- M. Valls
- Affiliation: Department de Matemàtica, Universitat de Lleida, Jaume II 69, 25001-Lleida, Spain
- Email: magda@eup.udl.es
- Received by editor(s): March 5, 2003
- Received by editor(s) in revised form: May 3, 2003
- Published electronically: March 4, 2004
- Additional Notes: The first, second and fourth authors were supported in part by grant BFM2000-1113-C02-02.
The third author was supported in part by grant BFM2000-0794-C02-02. - © Copyright 2004 American Mathematical Society
- Journal: Math. Comp. 74 (2005), 411-427
- MSC (2000): Primary 11G20
- DOI: https://doi.org/10.1090/S0025-5718-04-01640-0
- MathSciNet review: 2085900