|
Determining the  -Sylow subgroup of an elliptic curve over a finite field
Author(s):
J.
Miret;
R.
Moreno;
A.
Rio;
M.
Valls.
Journal:
Math. Comp.
74
(2005),
411-427.
MSC (2000):
Primary 11G20
Posted:
March 4, 2004
Retrieve article in:
PDF
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  -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:
-
- 1.
- E. Bach and J. Shallit, Algorithmic Number Theory. Vol. 1: Efficient Algorithms, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996. MR 97e:11157
- 2.
- J. M. Couveignes and F. Morain, Schoof algorithm and isogeny cycles, ANTS-I (L. Adleman and M.D. Huangs, eds.), LNCS, no. 877, Springer-Verlag, 1994, pp. 43-58. MR 95m:11147
- 3.
- M. Fouquet, Anneau d'endomorphismes et cardinalité des courbes elliptiques: aspects algorithmiques, Ph.D. thesis, École Polytechnique, Paris, 2001.
- 4.
- 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.
- 5.
- D. Husemöller, Elliptic curves, GTM, no. 111, Springer-Verlag, 1987. MR 88h:11039
- 6.
- E. W. Knudsen, Elliptic scalar multiplication using point halving, Advances in Cryptology-ASIACRYPT'99 (K.Y. Lam, E. Okamoto, and C. Xing, eds.), LNCS, no. 1716, Springer-Verlag, 1999, pp. 135-149. MR 2001d:94016
- 7.
- 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.
- 8.
- J. F. Mestre, La méthode des graphes. Exemples et applications, Proc. Int. Conf. on Class Numbers and Fundamental Units of Algebraic Number Fields (Katata, Japan), 1986, pp. 217-242. MR 88e:11025
- 9.
- 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. Journal 2 (2002), no. 9, 931-942. MR 2003e:11066
- 10.
- H. G. Rück, A note on elliptic curves over finite fields, Math. of Comp. 49 (1987), no. 179, 301-304. MR 88d:11058
- 11.
- R. Schoof, Nonsingular plane cubic curves over finite fields, J. Comb. Theory Ser. A 46 (1987), 183-211. MR 88k:14013
- 12.
- J. H. Silverman, The arithmetic of elliptic curves, GTM, no. 106, Springer-Verlag, 1986. MR 87g:11070
- 13.
- J. Voloch, A note on elliptic curves over finite fields, Bull. Soc. Math. France (1988), no. 116, 455-458. MR 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@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:
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
Posted:
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 of article:
Copyright
2004,
American Mathematical Society
|
Comments: webmaster@ams.org