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

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.

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.

DOI : 10.5802/jtnb.460
Enge, Andreas 1 ; Schertz, Reinhard 2

1 INRIA Futurs & LIX (CNRS/UMR 7161) École polytechnique 91128 Palaiseau cedex, France
2 Institut für Mathematik Universität Augsburg 86135 Augsburg, Deutschland
@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},
     pages = {555--568},
     publisher = {Universit\'e Bordeaux 1},
     volume = {16},
     number = {3},
     year = {2004},
     doi = {10.5802/jtnb.460},
     zbl = {1072.11039},
     mrnumber = {2144957},
     language = {en},
     url = {http://archive.numdam.org/articles/10.5802/jtnb.460/}
}
TY  - JOUR
AU  - Enge, Andreas
AU  - Schertz, Reinhard
TI  - Constructing elliptic curves over finite fields using double eta-quotients
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2004
SP  - 555
EP  - 568
VL  - 16
IS  - 3
PB  - Université Bordeaux 1
UR  - http://archive.numdam.org/articles/10.5802/jtnb.460/
DO  - 10.5802/jtnb.460
LA  - en
ID  - JTNB_2004__16_3_555_0
ER  - 
%0 Journal Article
%A Enge, Andreas
%A Schertz, Reinhard
%T Constructing elliptic curves over finite fields using double eta-quotients
%J Journal de théorie des nombres de Bordeaux
%D 2004
%P 555-568
%V 16
%N 3
%I Université Bordeaux 1
%U http://archive.numdam.org/articles/10.5802/jtnb.460/
%R 10.5802/jtnb.460
%G en
%F 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, Tome 16 (2004) no. 3, pp. 555-568. doi : 10.5802/jtnb.460. http://archive.numdam.org/articles/10.5802/jtnb.460/

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

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

[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

[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 | Zbl

[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 | Zbl

[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

[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 | Zbl

[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

[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 | Zbl

[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 | Zbl

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

[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

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

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

Cité par Sources :