Generalized class polynomials

Research in Number Theory, vol. 8

Abstract

Abstract The Hilbert class polynomial has as roots the j-invariants of elliptic curves whose endomorphism ring is a given imaginary quadratic order. It can be used to compute elliptic curves over finite fields with a prescribed number of points. Since its coefficients are typically rather large, there has been continued interest in finding alternative modular functions whose corresponding class polynomials are smaller. Best known are Weber’s functions, which reduce the size by a factor of 72 for a positive density subset of imaginary quadratic discriminants. On the other hand, Bröker and Stevenhagen showed that no modular function will ever do better than a factor of 100.83. We introduce a generalization of class polynomials, with reduction factors that are not limited by the Bröker–Stevenhagen bound. We provide examples matching Weber’s reduction factor. For an infinite family of discriminants, their reduction factors surpass those of all previously known modular functions by a factor at least 2.

Authors 2

1. Marc Houben corresponding Aachen Mathematisch Instituut

   Leiden University · KU Leuven · IMEC

   Affiliation as printed

   Departement Wiskunde, KU Leuven, Celestijnenlaan 200B – bus 2400, 3001, Leuven, Belgium

   Mathematisch Instituut, Universiteit Leiden, P.O. Box 9512, 2300 RA, Leiden, The Netherlands

   imec-COSIC, KU Leuven, Kasteelpark Arenberg 10/2452, 3001, Leuven, Belgium

2. Marco Streng Aachen Mathematisch Instituut

   Leiden University

   Affiliation as printed

   Mathematisch Instituut, Universiteit Leiden, P.O. Box 9512, 2300 RA, Leiden, The Netherlands