×

Computing isogenies between elliptic curves over \(F_{p^n}\) using Couveignes’s algorithm. (English) Zbl 0963.11032

Elliptic curves over finite fields have been used to factor integers [cf. H. W. Lenstra jun., Ann. Math. (2) 126, 649-673 (1987; Zbl 0629.10006) and P. L. Montgomery, Math. Comput. 48, 243-264 (1987; Zbl 0608.10005)]. One of the important steps in the solution of this problem is to compute the number of elliptic curves over a given finite field. Schoof’s polynomial time algorithm to solve this problem was efficiently implemented due to the work of A. O. L. Atkin [The number of points on an elliptic curve modulo a prime, draft (1988), http://listserv.nodak.edu./archives/nmbry.html] and N. D. Elkies [Explicit isogenies, draft (1991) and Elliptic and modular curves over finite fields and related computational issues, in Computational Perspectives in Number Theory, AMS/IP Stud. Adv. Math. 7, 21-76 (1998; Zbl 0915.11036)]. The methods used were good for large characteristics, however could not be used when the characteristic is small. The first answer to this situation appeared in Couveigne’s thesis [J.-M. Couveignes, Quelques calculs en théorie de nombres, Thèse, Université Bordeaux I, July 1994].
The aim of the paper under review is to explain how Couveigne’s algorithm can be implemented in an efficient way.

MSC:

11G20 Curves over finite and local fields
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
94A60 Cryptography
11Y16 Number-theoretic algorithms; complexity

Software:

ECPP; gfun
PDFBibTeX XMLCite
Full Text: DOI

References:

[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 (1993), no. 203, 29 – 68. · Zbl 0792.11056
[4] A. Borel, S. Chowla, C. S. Herz, K. Iwasawa, and J.-P. Serre, Seminar on complex multiplication, Seminar held at the Institute for Advanced Study, Princeton, N.J., 1957-58. Lecture Notes in Mathematics, No. 21, Springer-Verlag, Berlin-New York, 1966. · Zbl 0147.03902
[5] W. Bosma, Primality testing using elliptic curves, Tech. Rep. 85-12, Math. Institut, Universiteit van Amsterdam, 1985.
[6] 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. · Zbl 0475.65018 · doi:10.1016/0196-6774(80)90013-9
[7] R. P. Brent and H. T. Kung, Fast algorithms for manipulating formal power series, J. Assoc. Comput. Mach. 25 (1978), no. 4, 581 – 595. · Zbl 0388.68052 · doi:10.1145/322092.322099
[8] L. Comtet, Calcul pratique des coefficients de Taylor d’une fonction algébrique, Enseignement Math. (2) 10 (1964), 267 – 270 (French). · Zbl 0166.41702
[9] J.-M. Couveignes, Quelques calculs en théorie des nombres, Thèse, Université de Bordeaux I, July 1994.
[10] Jean-Marc Couveignes, Computing \?-isogenies using the \?-torsion, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 59 – 65. · Zbl 0903.11030 · doi:10.1007/3-540-61581-4_41
[11] -, Isomorphisms between Artin-Schreier towers. Draft, available on http://www.math.u-bordeaux.fr/\(^\sim\)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] 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. · Zbl 0849.14024 · doi:10.1007/3-540-58691-1_42
[14] M. Deuring, Die Typen der Multiplikatorenringe elliptischer Funktionenkörper, Abh. Math. Sem. Hamburg 14 (1941), 197-272. · Zbl 0025.02003
[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. · JFM 46.0599.02
[19] A. Fröhlich, Formal groups, Lecture Notes in Mathematics, No. 74, Springer-Verlag, Berlin-New York, 1968. · Zbl 0177.04801
[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] Hiroshi Gunji, The Hasse invariant and \?-division points of an elliptic curve, Arch. Math. (Basel) 27 (1976), no. 2, 148 – 158. · Zbl 0342.14008 · doi:10.1007/BF01224654
[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. · Zbl 0787.94017
[23] Dale Husemoller, Elliptic curves, Graduate Texts in Mathematics, vol. 111, Springer-Verlag, New York, 1987. With an appendix by Ruth Lawrence. · Zbl 0605.14032
[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 · Zbl 0955.11018
[25] Neal Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), no. 177, 203 – 209. · Zbl 0622.94015
[26] 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. · Zbl 0839.11026 · doi:10.1007/3-540-58691-1_44
[27] H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649 – 673. · Zbl 0629.10006 · doi:10.2307/1971363
[28] Reynald Lercier, Computing isogenies in \?_{2\(^{n}\)}, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 197 – 212. · Zbl 0911.11029 · doi:10.1007/3-540-61581-4_55
[29] -, Algorithmique des courbes elliptiques dans les corps finis, Thèse, École polytecnique, June 1997.
[30] 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. · Zbl 0903.11029 · doi:10.1007/3-540-49264-X_7
[31] 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. · Zbl 0903.11029 · doi:10.1007/3-540-49264-X_7
[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 · Zbl 0922.11110
[33] James L. Massey, Shift-register synthesis and \?\?\? decoding, IEEE Trans. Information Theory IT-15 (1969), 122 – 127. · Zbl 0167.18101
[34] 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. · Zbl 0662.94014
[35] Alfred Menezes and Scott Vanstone, Isomorphism classes of elliptic curves over finite fields of characteristic 2, Utilitas Math. 38 (1990), 135 – 153. · Zbl 0727.14021
[36] A. J. Menezes, Elliptic curve public key cryptosystems, Kluwer Academic Publishers, 1993. · Zbl 0806.94011
[37] Alfred J. Menezes, Scott A. Vanstone, and Robert J. Zuccherato, Counting points on elliptic curves over \?_{2^{\?}}, Math. Comp. 60 (1993), no. 201, 407 – 420. · Zbl 0809.14045
[38] 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. · doi:10.1007/3-540-39799-X_31
[39] Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), no. 177, 243 – 264. · Zbl 0608.10005
[40] Sunghan Bae and Ja Kyung Koo, Genus theory for function fields, J. Austral. Math. Soc. Ser. A 60 (1996), no. 3, 301 – 310. · Zbl 0857.11061
[41] -, Classes d’isomorphismes des courbes elliptiques supersingulières en caractéristique \(\geq 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. · Zbl 0888.65010
[44] 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). · Zbl 0852.11073
[45] J. H. Silverman, The arithmetic of elliptic curves, vol. 106 of Graduate Texts in Mathematics, Springer, 1986. · Zbl 0585.14026
[46] John Tate, Endomorphisms of abelian varieties over finite fields, Invent. Math. 2 (1966), 134 – 144. · Zbl 0147.20303 · doi:10.1007/BF01404549
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.