Constructing elliptic curves over finite fields using double eta-quotients
Journal de théorie des nombres de Bordeaux, Volume 16 (2004) no. 3, p. 555-568

We examine a class of modular functions for Γ 0 (N) whose values generate ring class fields of imaginary quadratic orders. This fact leads to a new algorithm for constructing elliptic curves with complex multiplication. The difficulties arising when the genus of X 0 (N) is not zero are overcome by computing certain modular polynomials.

Being a product of four η-functions, the proposed modular functions can be viewed as a natural generalisation of the functions examined by Weber and usually employed to construct CM-curves. Unlike the Weber functions, the values of the examined functions generate any ring class field of an imaginary quadratic order regardless of the congruences modulo powers of 2 and 3 satisfied by the discriminant.

Nous examinons une classe de fonctions modulaires pour Γ 0 (N) dont les valeurs engendrent des corps de classes d’anneaux d’ordres quadratiques imaginaires. Nous nous en servons pour développer un nouvel algorithme de construction de courbes elliptiques à multiplication complexe. Vu que le genre des X 0 (N) associées n’est pas zéro, le calcul de la courbe se fait à l’aide de certains polynômes modulaires.

Étant un produit de quatre fonctions η, les fonctions modulaires proposées peuvent être vues comme une généralisation naturelle des fonctions traitées par Weber et généralement utilisées pour construire des courbes elliptiques à multiplication complexes. Contrairement au cas des fonctions de Weber, les valeurs des fonctions examinées ici engendrent tous les corps de classes d’anneaux de n’importe quel ordre quadratique imaginaire sans tenir compte des congruences satisfaites par leur discriminant modulo des puissances de 2 ou 3.

@article{JTNB_2004__16_3_555_0,
     author = {Enge, Andreas and Schertz, Reinhard},
     title = {Constructing elliptic curves over finite fields using double eta-quotients},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Universit\'e Bordeaux 1},
     volume = {16},
     number = {3},
     year = {2004},
     pages = {555-568},
     doi = {10.5802/jtnb.460},
     mrnumber = {2144957},
     zbl = {1072.11039},
     language = {en},
     url = {http://www.numdam.org/item/JTNB_2004__16_3_555_0}
}
Enge, Andreas; Schertz, Reinhard. Constructing elliptic curves over finite fields using double eta-quotients. Journal de théorie des nombres de Bordeaux, Volume 16 (2004) no. 3, pp. 555-568. doi : 10.5802/jtnb.460. http://www.numdam.org/item/JTNB_2004__16_3_555_0/

[1] A. O. L. Atkin, F. Morain, Elliptic curves and primality proving. Mathematics of Computation, 61(203) (July 1993), 29–68. | MR 1199989 | Zbl 0792.11056

[2] Z. I. Borevich, I. R. Shafarevich, Number Theory. Pure and Applied Mathematics, Academic Press, New York, 1966. | MR 195803 | Zbl 0145.04902

[3] David A. Cox, Primes of the Form x 2 +ny 2 — Fermat, Class Field Theory, and Complex Multiplication. John Wiley & Sons, New York, 1989. | Zbl 0701.11001

[4] R. Dedekind, Erläuterungen zu den vorstehenden Fragmenten. In R. Dedekind and H. Weber, editors, Bernhard Riemann’s gesammelte mathematische Werke und wissenschaftlicher Nachlaß, pages 438–447. Teubner, Leipzig, 1876.

[5] Max Deuring, Die Typen der Multiplikatorenringe elliptischer Funktionenkörper. Abhandlungen aus dem mathematischen Seminar der hamburgischen Universität 14 (1941), 197–272. | MR 5125 | Zbl 0025.02003

[6] Max Deuring, Die Klassenkörper der komplexen Multiplikation. In Enzyklop. d. math. Wissenschaften, volume I 2 Heft 10. Teubner, Stuttgart, 2 edition, 1958. | MR 167481 | Zbl 0123.04001

[7] Andreas Enge, Elliptic Curves and Their Applications to Cryptography — An Introduction. Kluwer Academic Publishers, 1999.

[8] Andreas Enge, François Morain, Comparing invariants for class fields of imaginary quadratic fields. In Claus Fieker and David R. Kohel, editors, Algorithmic Number Theory — ANTS-V, volume 2369 of Lecture Notes in Computer Science, pages 252–266, Berlin, 2002. Springer-Verlag. | Zbl 1058.11077

[9] Andreas Enge, François Morain, Further investigations of the generalised Weber functions. In preparation, 2005.

[10] Andreas Enge, Reinhard Schertz, Modular curves of composite level. To appear in Acta Arithmetica, 2005. | MR 2141046 | Zbl 02203394

[11] Andreas Enge, Paul Zimmermann, mpc — a library for multiprecision complex arithmetic with exact rounding. Version 0.4.3, available from http://www.lix.polytechnique.fr/Labo/Andreas.Enge/Software.html.

[12] Mireille Fouquet, François Morain, Isogeny volcanoes and the SEA algorithm. In Claus Fieker and David R. Kohel, editors, Algorithmic Number Theory — ANTS-V, volume 2369 of Lecture Notes in Computer Science, pages 276–291, Berlin, 2002. Springer-Verlag. | Zbl 1058.11041

[13] Shafi Goldwasser, Joe Kilian. Almost all primes can be quickly certified. In Proc. 18th Annual ACM Symp. on Theory of Computing, pages 316–329, 1986.

[14] Torbjörn Granlund et. al., gmp — GNU multiprecision library. Version 4.1.4, available from http://www.swox.com/gmp.

[15] Guillaume Hanrot, Vincent Lefèvre, Paul Zimmermann et. al., mpfr — a library for multiple-precision floating-point computations with exact rounding. Version 2.1.0, available from http://www.mpfr.org.

[16] Carl Gustav Jacob Jacobi, Fundamenta nova theoriae functionum ellipticarum. In Gesammelte Werke, pages 49–239. Chelsea, New York, 2 (1969) edition, 1829.

[17] Neal Koblitz Elliptic curve cryptosystems. Mathematics of Computation 48(177) (January 1987), 203–209. | MR 866109 | Zbl 0622.94015

[18] David Kohel Endomorphism Rings of Elliptic Curves over Finite Fields. PhD thesis, University of California at Berkeley, 1996.

[19] Georg-Johann Lay, Horst G. Zimmer, Constructing elliptic curves with given group order over large finite fields. In Leonard M. Adleman and Ming-Deh Huang, editors, Algorithmic Number Theory, volume 877 of Lecture Notes in Computer Science, pages 250–263, Berlin, 1994. Springer-Verlag. | MR 1322728 | Zbl 0833.11024

[20] H. W. Lenstra Jr., Factoring integers with elliptic curves. Annals of Mathematics 126 (1987), 649–673. | MR 916721 | Zbl 0629.10006

[21] Victor S. Miller, Use of elliptic curves in cryptography. In Hugh C. Williams, editor, Advances in Cryptology — CRYPTO ’85, volume 218 of Lecture Notes in Computer Science, pages 417–426, Berlin, 1986. Springer-Verlag. | Zbl 0589.94005

[22] Morris Newman, Construction and application of a class of modular functions (II). Proceedings of the London Mathematical Society 3rd Series 9 (1959), 373–387. | MR 107629 | Zbl 0178.43001

[23] Reinhard Schertz, Zur expliziten Berechnung von Ganzheitsbasen in Strahlklassenkörpern über einem imaginär-quadratischen Zahlkörper. Journal of Number Theory 34(1) (January 1990), 41–53. | MR 1039766 | Zbl 0701.11059

[24] Reinhard Schertz, Weber’s class invariants revisited, Journal de Théorie des Nombres de Bordeaux 14(1) (2002), 325–343. | Numdam | MR 1926005 | Zbl 1022.11056

[25] Victor Shoup, ntl — a library for doing number theory. Version 5.3.2, available from http://www.shoup.net/ntl/.

[26] Joseph H. Silverman, The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics. Springer-Verlag, New York, 1986. | MR 817210 | Zbl 0585.14026

[27] Heinrich Weber, Lehrbuch der Algebra, volume 3. Chelsea Publishing Company, New York, 3rd edition, 1908.