Computing isogenies between elliptic curves over 𝐹_{𝑝ⁿ} using Couveignes’s algorithm

Lercier, R.; Morain, F.

doi:10.1090/S0025-5718-99-01081-9

Computing isogenies between elliptic curves over $F_{p^n}$ using Couveignes’s algorithm
HTML articles powered by AMS MathViewer

by R. Lercier and F. Morain PDF

Math. Comp. 69 (2000), 351-370 Request permission

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.

References

A. O. L. Atkin, The number of points on an elliptic curve modulo a prime, Draft, 1988.
—, The number of points on an elliptic curve modulo a prime (ii), Draft. Available on http://listserv.nodak.edu/archives/nmbrthry.html, 1992.
A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), no. 203, 29–68. MR 1199989, DOI 10.1090/S0025-5718-1993-1199989-X
A. Borel, S. Chowla, C. S. Herz, K. Iwasawa, and J.-P. Serre, Seminar on complex multiplication, Lecture Notes in Mathematics, No. 21, Springer-Verlag, Berlin-New York, 1966. Seminar held at the Institute for Advanced Study, Princeton, N.J., 1957-58. MR 0201394
W. Bosma, Primality testing using elliptic curves, Tech. Rep. 85-12, Math. Institut, Universiteit van Amsterdam, 1985.
Richard P. Brent, Fred G. Gustavson, and David Y. Y. Yun, Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms 1 (1980), no. 3, 259–295. MR 604867, DOI 10.1016/0196-6774(80)90013-9
R. P. Brent and H. T. Kung, Fast algorithms for manipulating formal power series, J. Assoc. Comput. Mach. 25 (1978), no. 4, 581–595. MR 520733, DOI 10.1145/322092.322099
L. Comtet, Calcul pratique des coefficients de Taylor d’une fonction algébrique, Enseign. Math. (2) 10 (1964), 267–270 (French). MR 164441
J.-M. Couveignes, Quelques calculs en théorie des nombres, Thèse, Université de Bordeaux I, July 1994.
Jean-Marc Couveignes, Computing $l$-isogenies using the $p$-torsion, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 59–65. MR 1446498, DOI 10.1007/3-540-61581-4_{4}1
—, Isomorphisms between Artin-Schreier towers. Draft, available on http://www.math.u-bordeaux.fr/$^\sim$couveign, Jan. 1997.
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.
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
Sergio Sispanov, Generalización del teorema de Laguerre, Bol. Mat. 12 (1939), 113–117 (Spanish). MR 3
L. Dewaghe, Un corollaire aux formules de Vélu, Preprint, Dec. 1995.
N. D. Elkies, Explicit isogenies, Draft, 1991.
—, 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.
R. Fricke, Die elliptischen Funktionen und ihre Anwendungen, Teubner, Leipzig, 1992.
A. Fröhlich, Formal groups, Lecture Notes in Mathematics, No. 74, Springer-Verlag, Berlin-New York, 1968. MR 0242837
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.
Hiroshi Gunji, The Hasse invariant and $p$-division points of an elliptic curve, Arch. Math. (Basel) 27 (1976), no. 2, 148–158. MR 412198, DOI 10.1007/BF01224654
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.
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
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.
Neal Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), no. 177, 203–209. MR 866109, DOI 10.1090/S0025-5718-1987-0866109-5
Frank Lehmann, Markus Maurer, Volker Müller, and Victor Shoup, Counting the number of points on elliptic curves over finite fields of characteristic greater than three, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 60–70. MR 1322712, DOI 10.1007/3-540-58691-1_{4}4
H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI 10.2307/1971363
Reynald Lercier, Computing isogenies in $\textbf {F}_{2^n}$, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 197–212. MR 1446512, DOI 10.1007/3-540-61581-4_{5}5
—, Algorithmique des courbes elliptiques dans les corps finis, Thèse, École polytecnique, June 1997.
Reynald Lercier and François Morain, Counting the number of points on elliptic curves over finite fields: strategies and performances, Advances in cryptology—EUROCRYPT ’95 (Saint-Malo, 1995) Lecture Notes in Comput. Sci., vol. 921, Springer, Berlin, 1995, pp. 79–94. MR 1367512, DOI 10.1007/3-540-49264-X_{7}
Reynald Lercier and François Morain, Counting the number of points on elliptic curves over finite fields: strategies and performances, Advances in cryptology—EUROCRYPT ’95 (Saint-Malo, 1995) Lecture Notes in Comput. Sci., vol. 921, Springer, Berlin, 1995, pp. 79–94. MR 1367512, DOI 10.1007/3-540-49264-X_{7}
—, 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.
James L. Massey, Shift-register synthesis and $\textrm {BCH}$ decoding, IEEE Trans. Inform. Theory IT-15 (1969), 122–127. MR 242556, DOI 10.1109/tit.1969.1054260
Robert J. McEliece, Finite fields for computer scientists and engineers, The Kluwer International Series in Engineering and Computer Science, vol. 23, Kluwer Academic Publishers, Boston, MA, 1987. MR 884528, DOI 10.1007/978-1-4613-1983-2
Alfred Menezes and Scott Vanstone, Isomorphism classes of elliptic curves over finite fields of characteristic $2$, Utilitas Math. 38 (1990), 135–153. MR 1093882
A. J. Menezes, Elliptic curve public key cryptosystems, Kluwer Academic Publishers, 1993.
Alfred J. Menezes, Scott A. Vanstone, and Robert J. Zuccherato, Counting points on elliptic curves over $\mathbf F_{2^m}$, Math. Comp. 60 (1993), no. 201, 407–420. MR 1153167, DOI 10.1090/S0025-5718-1993-1153167-9
Victor S. Miller, Use of elliptic curves in cryptography, Advances in cryptology—CRYPTO ’85 (Santa Barbara, Calif., 1985) Lecture Notes in Comput. Sci., vol. 218, Springer, Berlin, 1986, pp. 417–426. MR 851432, DOI 10.1007/3-540-39799-X_{3}1
Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), no. 177, 243–264. MR 866113, DOI 10.1090/S0025-5718-1987-0866113-7
Sunghan Bae and Ja Kyung Koo, Genus theory for function fields, J. Austral. Math. Soc. Ser. A 60 (1996), no. 3, 301–310. MR 1385143
—, Classes d’isomorphismes des courbes elliptiques supersingulières en caractéristique $\ge 3$, Utilitas Math. 52 (1997), 241–253.
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.
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.
René Schoof, Counting points on elliptic curves over finite fields, J. Théor. Nombres Bordeaux 7 (1995), no. 1, 219–254. Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). MR 1413578
Radu Bǎdescu, On a problem of Goursat, Gaz. Mat. 44 (1939), 571–577. MR 0000087
John Tate, Endomorphisms of abelian varieties over finite fields, Invent. Math. 2 (1966), 134–144. MR 206004, DOI 10.1007/BF01404549