Constructing elliptic curves over finite fields using double eta-quotients

Andreas Enge[1]; Reinhard Schertz[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

Journal de Théorie des Nombres de Bordeaux (2004)

  • Volume: 16, Issue: 3, page 555-568
  • ISSN: 1246-7405

Abstract

top
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.

How to cite

top

Enge, Andreas, and Schertz, Reinhard. "Constructing elliptic curves over finite fields using double eta-quotients." Journal de Théorie des Nombres de Bordeaux 16.3 (2004): 555-568. <http://eudml.org/doc/249281>.

@article{Enge2004,
abstract = {We examine a class of modular functions for $\Gamma ^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 $\eta $-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.},
affiliation = {INRIA Futurs & LIX (CNRS/UMR 7161) École polytechnique 91128 Palaiseau cedex, France; Institut für Mathematik Universität Augsburg 86135 Augsburg, Deutschland},
author = {Enge, Andreas, Schertz, Reinhard},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {Weber function; ring class field; modular function},
language = {eng},
number = {3},
pages = {555-568},
publisher = {Université Bordeaux 1},
title = {Constructing elliptic curves over finite fields using double eta-quotients},
url = {http://eudml.org/doc/249281},
volume = {16},
year = {2004},
}

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
PB - Université Bordeaux 1
VL - 16
IS - 3
SP - 555
EP - 568
AB - We examine a class of modular functions for $\Gamma ^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 $\eta $-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.
LA - eng
KW - Weber function; ring class field; modular function
UR - http://eudml.org/doc/249281
ER -

References

top
  1. A. O. L. Atkin, F. Morain, Elliptic curves and primality proving. Mathematics of Computation, 61(203) (July 1993), 29–68. Zbl0792.11056MR1199989
  2. Z. I. Borevich, I. R. Shafarevich, Number Theory. Pure and Applied Mathematics, Academic Press, New York, 1966. Zbl0145.04902MR195803
  3. David A. Cox, Primes of the Form x 2 + n y 2 — Fermat, Class Field Theory, and Complex Multiplication. John Wiley & Sons, New York, 1989. Zbl0701.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. Zbl0025.02003MR5125
  6. Max Deuring, Die Klassenkörper der komplexen Multiplikation. In Enzyklop. d. math. Wissenschaften, volume I 2 Heft 10. Teubner, Stuttgart, 2 edition, 1958. Zbl0123.04001MR167481
  7. Andreas Enge, Elliptic Curves and Their Applications to Cryptography — An Introduction. Kluwer Academic Publishers, 1999. Zbl1335.11002
  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. Zbl1058.11077
  9. Andreas Enge, François Morain, Further investigations of the generalised Weber functions. In preparation, 2005. Zbl1319.11039
  10. Andreas Enge, Reinhard Schertz, Modular curves of composite level. To appear in Acta Arithmetica, 2005. Zbl1158.11322MR2141046
  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. Zbl1058.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 KoblitzElliptic curve cryptosystems. Mathematics of Computation 48(177) (January 1987), 203–209. Zbl0622.94015MR866109
  18. David KohelEndomorphism 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. Zbl0833.11024MR1322728
  20. H. W. Lenstra Jr., Factoring integers with elliptic curves. Annals of Mathematics 126 (1987), 649–673. Zbl0629.10006MR916721
  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. Zbl0589.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. Zbl0178.43001MR107629
  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. Zbl0701.11059MR1039766
  24. Reinhard Schertz, Weber’s class invariants revisited, Journal de Théorie des Nombres de Bordeaux 14(1) (2002), 325–343. Zbl1022.11056MR1926005
  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. Zbl0585.14026MR817210
  27. Heinrich Weber, Lehrbuch der Algebra, volume 3. Chelsea Publishing Company, New York, 3rd edition, 1908. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.