Determining the 2-Sylow subgroup of an elliptic curve over a finite field

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

doi:10.1090/S0025-5718-04-01640-0

Determining the $2$-Sylow subgroup 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. 74 (2005), 411-427 Request permission

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