Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

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


Authors: J. Miret, R. Moreno, A. Rio and M. Valls
Journal: Math. Comp. 74 (2005), 411-427
MSC (2000): Primary 11G20
Published electronically: March 4, 2004
MathSciNet review: 2085900
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)


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@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
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

DOI: http://dx.doi.org/10.1090/S0025-5718-04-01640-0
PII: S 0025-5718(04)01640-0
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.
Article copyright: © Copyright 2004 American Mathematical Society