Mathematics of Computation

Computing isogenies between elliptic curves over $F_{p^n}$ using Couveignes's algorithm

Author(s): R. Lercier; F. Morain.
Journal: Math. Comp. 69 (2000), 351-370.
MSC (1991): Primary 11G20; Secondary 11T71, 94A60, 11Y16
Posted: March 4, 1999
Retrieve article in: PDF DVI PostScript
This article is available free of charge

Abstract: The heart of the improvements by Elkies to Schoof's algorithm for computing the cardinality of elliptic curves over a finite field is the ability to compute isogenies between curves. Elkies' approach is well suited for the case where the characteristic of the field is large. Couveignes showed how to compute isogenies in small characteristic. The aim of this paper is to describe the first successful implementation of Couveignes's algorithm. In particular, we describe the use of fast algorithms for performing incremental operations on series. We also insist on the particular case of the characteristic 2.

1.: A. O. L. Atkin, The number of points on an elliptic curve modulo a prime, Draft, 1988.
2.: -, The number of points on an elliptic curve modulo a prime (ii), Draft. Available on http://listserv.nodak.edu/archives/nmbrthry.html, 1992.
3.: A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 203 (July 1993), 29-68. MR 93m:11136
4.: A. Borel, S. Chowla, C. S. Herz, K. Iwasawa, and J.-P. Serre, Seminar on complex multiplication, No. 21 in Lecture Notes in Math., Springer, 1966. MR 34:1278
5.: W. Bosma, Primality testing using elliptic curves, Tech. Rep. 85-12, Math. Institut, Universiteit van Amsterdam, 1985.
6.: R. P. Brent, F. G. Gustavson, and D. Y. Y. Yun, Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms 1 (1980), 259-295. MR 82d:65033
7.: R. P. Brent and H. T. Kung, Fast algorithms for manipulating formal power series, J. Assoc. Comput. Mach. 25 (1978), 581-595. MR 58:25090
8.: L. Comtet, Calcul pratique des coefficients de Taylor d'une fonction algébrique, Enseignement Math. 10 (1964), 267-270. MR 29:1738
9.: J.-M. Couveignes, Quelques calculs en théorie des nombres, Thèse, Université de Bordeaux I, July 1994.
10.: -, Computing $l$ -isogenies using the $p$ -torsion, In Algorithmic Number Theory (1996), H. Cohen, Ed., vol. 1122 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 59-65. Second International Symposium, ANTS-II, Talence, France, May 1996, Proceedings. MR 98j:11046
11.: -, Isomorphisms between Artin-Schreier towers. Draft, available on http://www.math.u-bordeaux.fr/couveign, Jan. 1997.
12.: J.-M. Couveignes, L. Dewaghe, and F. Morain, Isogeny cycles and the Schoof-Elkies-Atkin algorithm, Research Report LIX/RR/96/03, LIX, Apr. 1996.
13.: J.-M. Couveignes and F. Morain, Schoof's algorithm and isogeny cycles. In ANTS-I (1994), L. Adleman and M.-D. Huang, Eds., vol. 877 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 43-58. 1st Algorithmic Number Theory Symposium-Cornell University, May 6-9, 1994. MR 95m:11147
14.: M. Deuring, Die Typen der Multiplikatorenringe elliptischer Funktionenkörper, Abh. Math. Sem. Hamburg 14 (1941), 197-272. MR 3:104f
15.: L. Dewaghe, Un corollaire aux formules de Vélu, Preprint, Dec. 1995.
16.: N. D. Elkies, Explicit isogenies, Draft, 1991.
17.: -, Elliptic and modular curves over finite fields and related computational issues, In Computational Perspectives on Number Theory: Proceedings of a Conference in Honor of A. O. L. Atkin (1998), D. A. Buell and J. T. Teitelbaum, Eds., vol. 7 of AMS/IP Studies in Advanced Mathematics, American Mathematical Society, International Press. CMP 98:05
18.: R. Fricke, Die elliptischen Funktionen und ihre Anwendungen, Teubner, Leipzig, 1992.
19.: A. Fröhlich, Formal groups, vol. 74 of Lecture Notes in Math., Springer-Verlag, 1968. MR 39:4164
20.: S. Goldwasser and J. Kilian, Almost all primes can be quickly certified, In Proc. 18th STOC (1986), ACM, pp. 316-329. May 28-30, Berkeley.
21.: H. Gunji, The Hasse invariant and $p$ -division points of an elliptic curve, Arch. Math. 27 2 (1976), 148-158. MR 54:325
22.: G. Harper, A. Menezes, and S. Vanstone, Public-key cryptosystems with very small key length, In Advances in Cryptoloy - EUROCRYPT '92 (1993), R. A. Rueppel, Ed., vol. 658 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 163-173. Workshop on the Theory and Application of Cryptographic Techniques, Balatonfüred, Hungary, May 24-28, 1992, Proceedings.
23.: D. Husemöller, Elliptic curves, vol. 111 of Graduate Texts in Mathematics, Springer, 1987. MR 88h:11039
24.: M. Kaneko and D. Zagier, Supersingular $j$ -invariants, hypergeometric series, and Atkin's orthogonal polynomials. In Computational Perspectives on Number Theory: Proceedings of a Conference in Honor of A. O. L. Atkin (1998), D. A. Buell and J. T. Teitelbaum, Eds., vol. 7 of AMS/IP Studies in Advanced Mathematics, American Mathematical Society, International Press. CMP 98:05
25.: N. Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 177 (Jan. 1987), 203-209. MR 88b:94017
26.: F. Lehmann, M. Maurer, V. Müller, and V. Shoup, Counting the number of points on elliptic curves over finite fields of characteristic greater than three. In ANTS-I (1994), L. Adleman and M.-D. Huang, Eds., vol. 877 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 60-70. 1st Algorithmic Number Theory Symposium-Cornell University, May 6-9, 1994. MR 95m:11148
27.: H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), 649-673. MR 89g:11125
28.: R. Lercier, Computing isogenies in $F_{2^n}$ , In Algorithmic Number Theory (1996), H. Cohen, Ed., vol. 1122 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 197-212. Second International Symposium, ANTS-II, Talence, France, May 1996, Proceedings. MR 98d:11069
29.: -, Algorithmique des courbes elliptiques dans les corps finis, Thèse, École polytecnique, June 1997.
30.: R. Lercier and F. Morain, Counting points on elliptic curves over $F_{p^n}$ using Couveignes's algorithm, Research Report LIX/RR/95/09, École Polytechnique-LIX, Sept. 1995. MR 96h:11060
31.: -, Counting the number of points on elliptic curves over finite fields: strategies and performances, In Advances in Cryptology - EUROCRYPT '95 (1995), L. C. Guillou and J.-J. Quisquater, Eds., vol. 921 of Lecture Notes in Comput. Sci., pp. 79-94. International Conference on the Theory and Application of Cryptographic Techniques, Saint-Malo, France, May 1995, Proceedings. MR 96h:11060
32.: -, Algorithms for computing isogenies between elliptic curves, In Computational Perspectives on Number Theory: Proceedings of a Conference in Honor of A. O. L. Atkin (1998), D. A. Buell and J. T. Teitelbaum, Eds., vol. 7 of AMS/IP Studies in Advanced Mathematics, American Mathematical Society, International Press. CMP 98:05
33.: J. L. Massey, Shift-register and BCH decoding, IEEE Trans. Inform. Theory IT-15, 1 (Jan. 1969), 122-127. MR 39:3887
34.: R. McEliece, Finite fields for computer scientists and engineers, Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, 1988. MR 88h:11091
35.: A. Menezes and S. Vanstone, Isomorphism classes of elliptic curves over finite fields of characteristic 2, Utilitas Math. 38 (1990), 135-153. MR 92a:11071
36.: A. J. Menezes, Elliptic curve public key cryptosystems, Kluwer Academic Publishers, 1993.
37.: A. J. Menezes, S. A. Vanstone, and R. J. Zuccherato, Counting points on elliptic curves over $F_{2^m}$ , Math. Comp. 60, 201 (Jan. 1993), 407-420. MR 93f:11098
38.: V. Miller, Use of elliptic curves in cryptography, In Advances in Cryptology - CRYPTO '86 (1987), A. M. Odlyzko, Ed., vol. 263 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 417-426. Proceedings, Santa Barbara (USA), August 11-15, 1986. MR 88b:68040
39.: P. L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48, 177 (Jan. 1987), 243-264. MR 88e:11130
40.: F. Morain, Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques, J. Théor. Nombres Bordeaux 7 (1995), 255-282. MR 97i:11111
41.: -, Classes d'isomorphismes des courbes elliptiques supersingulières en caractéristique $\ge 3$ , Utilitas Math. 52 (1997), 241-253. CMP 98:08
42.: V. Müller, Ein Algorithmus zur Bestimmung der Punktanzahl elliptischer Kurven über endlichen Körpern der Charakteristik größer drei, Ph.D. thesis, Technischen Fakultät der Universität des Saarlandes, 1995.
43.: B. Salvy, P. Zimmermann, and P. Gfun, A maple package for the manipulation of generating and holonomic functions in one variable, ACM Transactions on Mathematical Software 20, 2 (1994), 163-177.
44.: R. Schoof, Counting points on elliptic curves over finite fields, J. Théor. Nombes Bordeaux 7 (1995), 219-254. MR 97i:11070
45.: J. H. Silverman, The arithmetic of elliptic curves, vol. 106 of Graduate Texts in Mathematics, Springer, 1986. MR 87g:11061
46.: J. Tate, Endomorphisms of Abelian varieties over finite fields, Invent. Math. 2 (1966), 134-144. MR 34:5829

Retrieve articles in Mathematics of Computation with MSC (1991): 11G20, 11T71, 94A60, 11Y16

R. Lercier
Affiliation: CELAR/SSIG, Route de Laillé, F-35170 Bruz, France
Email: lercier@celar.fr

F. Morain
Affiliation: Laboratoire d'Informatique de l'École polytechnique (LIX - UMR 7650), F-91128 Palaiseau Cedex, France
Email: morain@lix.polytechnique.fr

DOI: 10.1090/S0025-5718-99-01081-9
PII: S 0025-5718(99)01081-9
Keywords: Elliptic curves, finite fields, isogenies, formal groups, Schoof's algorithm
Received by editor(s): May 6, 1996
Received by editor(s) in revised form: March 10, 1998
Posted: March 4, 1999
Additional Notes: The second author is on leave from the French Department of Defense, Délégation Générale pour l'Armement
Copyright of article: Copyright 1999, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS