Article Contents
Article Contents

# Some remarks on the construction of class polynomials

• Class invariants are singular values of modular functions which generate the class fields of imaginary quadratic number fields. Their minimal polynomials, called class polynomials, are uniquely determined by a discriminant $-D<0$ and are used in many applications, including the generation of elliptic curves. In all these applications, it is desirable that the size of the polynomials is as small as possible. Among all known class polynomials, Weber polynomials constructed with discriminants $-D \equiv 1$ (mod $8$) have the smallest height and require the least precision for their construction. In this paper, we will show that this fact does not necessarily lead to the most efficient computations, since the congruences modulo $8$ of the discriminants affect the degrees of the polynomials.
Mathematics Subject Classification: Primary: 11R29; Secondary: 94A60, 11T71.

 Citation:

•  [1] L. V. Ahlfors, "Complex Analysis. An Introduction to the Theory of Analytic Functions of One Complex Variable,'' $3^{rd}$ edition, McGraw-Hill Book Co., New York, 1978. [2] J. Belding, R. Bröker, A. Enge and K. Lauter, Computing Hilbert class polynomials, in "Algorithmic Number Theory Symposium - ANTS 2008,'' Springer-Verlag, (2008), 282-295. [3] W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: the user language, J. Symbolic Comput., 24 (1997), 235-265.doi: 10.1006/jsco.1996.0125. [4] R. Bröker, A $p$-adic algorithm to compute the Hilbert class polynomial, Math. Compu., 77 (2008), 2417-2435.doi: 10.1090/S0025-5718-08-02091-7. [5] A. Enge, The complexity of class polynomial computation via floating point approximations, Math. Compu., 78 (2009), 1089-1107.doi: 10.1090/S0025-5718-08-02200-X. [6] A. Enge and F. Morain, Comparing invariants for class fields of imaginary quadratic fields, in "Algorithmic Number Theory Symposium - ANTS 2002,'' Springer-Verlag, (2002), 252-266. [7] A. Enge and R. Schertz, Constructing elliptic curves over finite fields using double eta-quotients, J. Théor. Nombres Bordeaux, 16 (2004), 555-568. [8] A. Enge and A. V. Sutherland, Class invariants for the CRT method, in "Algorithmic Number Theory Symposium - ANTS 2010,'' Springer-Verlag, (2010), 142-156. [9] E. Konstantinou and A. Kontogeorgis, Computing polynomials of the Ramanujan $t_n$ class invariants, Canadian Math. Bull., 52 (2009), 583-597.doi: 10.4153/CMB-2009-058-6. [10] E. Konstantinou and A. Kontogeorgis, Ramanujan's class invariants and their use in elliptic curve cryptography, Comput. Math. Appl., 59 (2010), 2901-2917.doi: 10.1016/j.camwa.2010.02.008. [11] G. J. Lay and H. Zimmer, Constructing elliptic curves with given group order over large finite fields, in "Algorithmic Number Theory - ANTS-I,'' Springer-Verlag, (1994), 250-263. [12] F. Morain, Modular curves and class invariants, preprint. [13] F. Morain, Advances in the CM method for elliptic curves, in "Slides of Fields Cryptography Retrospective Meeting,'' (2009); available online at http://www.lix.polytechnique.fr/~morain/Exposes/fields09.pdf [14] W. Narkiewicz, "Elementary and Analytic Theory of Algebraic Numbers,'' $2^{nd}$ edition, Springer-Verlag, 1990. [15] R. Schertz, Weber's class invariants revisited, J. Théor. Nombres Bordeaux, 4 (2002), 325-343. [16] A. V. Sutherland, Computing Hilbert class polynomials with the Chinese Remainder Theorem, Math. Compu., to appear; preprint, arXiv:0903.2785