Abstract
We adapt the CRT approach for computing Hilbert class polynomials to handle a wide range of class invariants. For suitable discriminants D, this improves its performance by a large constant factor, more than 200 in the most favourable circumstances. This has enabled record-breaking constructions of elliptic curves via the CM method, including examples with |D| > 1015.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bach, E.: Explicit bounds for primality testing and related problems. Mathematics of Computation 55(191), 355–380 (1990)
Belding, J., Bröker, R., Enge, A., Lauter, K.: Computing Hilbert class polynomials. In: van der Poorten, A.J., Stein, A. (eds.) ANTS-VIII 2008. LNCS, vol. 5011, pp. 282–295. Springer, Heidelberg (2008)
Berndt, B.C., Chan, H.H.: Ramanujan and the modular j-invariant. Canadian Mathematical Bulletin 42(4), 427–440 (1999)
Bernstein, D.J.: Modular exponentiation via the explicit Chinese Remainder Theorem. Mathematics of Computation 76, 443–454 (2007)
Bisson, G., Sutherland, A.V.: Computing the endomorphism ring of an ordinary elliptic curve over a finite field. Journal of Number Theory (2009) (to appear), http://arxiv.org/abs/0902.4670
Bröker, R.: Constructing elliptic curves of prescribed order. Universiteit Leiden, Proefschrift (2006)
Bröker, R.: A p-adic algorithm to compute the Hilbert class polynomial. Mathematics of Computation 77, 2417–2435 (2008)
Bröker, R., Lauter, K., Sutherland, A.V.: Modular polynomials via isogeny volcanoes (2009) (preprint), http://arxiv.org/abs/1001.0402
Couveignes, J.-M., Henocq, T.: Action of modular correspondences around CM points. In: Fieker, C., Kohel, D.R. (eds.) ANTS 2002. LNCS, vol. 2369, pp. 234–243. Springer, Heidelberg (2002)
Elkies, N.D.: Elliptic and modular curves over finite fields and related computational issues. In: Buell, D.A., Teitelbaum, J.T. (eds.) Computational Perspectives on Number Theory, pp. 21–76. AMS, Providence (1998)
Enge, A.: Courbes algébriques et cryptologie. In: Habilitation à diriger des recherches, vol. 7. Université Denis Diderot, Paris (2007)
Enge, A.: The complexity of class polynomial computation via floating point approximations. Mathematics of Computation 78(266), 1089–1107 (2009)
Enge, A.: Computing modular polynomials in quasi-linear time. Mathematics of Computation 78(267), 1809–1824 (2009)
Enge, A.: cm, 0.2 edition (2010), http://cm.multiprecision.org/
Enge, A., Morain, F.: Generalised Weber functions. I. Technical Report 385608, HAL-INRIA (2009), http://hal.inria.fr/inria-00385608
Enge, A., Schertz, R.: Constructing elliptic curves over finite fields using double eta-quotients. Journal de Théorie des Nombres de Bordeaux 16, 555–568 (2004)
Enge, A., Schertz, R.: Modular curves of composite level. Acta Arithmetica 118(2), 129–141 (2005)
Enge, A., Schertz, R.: Singular values of multiple eta-quotients for ramified primes (in preparation 2010)
Free Software Foundation. GNU Compiler Collection, 4.2.4 edition (2008), http://gcc.gnu.org/
Gee, A.: Class fields by Shimura reciprocity. Universiteit Leiden, Proefschrift (2001)
Gee, A., Stevenhagen, P.: Generating class fields using Shimura reciprocity. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 441–453. Springer, Heidelberg (1998)
Granlund, T., et al.: gmp, 4.3.1 edition (2009). http://gmplib.org/ .
Hajir, F., Villegas, F.R.: Explicit elliptic units, I. Duke Mathematical Journal 90(3), 495–521 (1997)
Harvey, D.: \(\text{zn\_poly}\): a library for polynomial arithmetic, 0.9 edn. (2008), http://cims.nyu.edu/~harvey/zn_poly
Kohel, D.: Endomorphism rings of elliptic curves over finite fields. PhD thesis, University of California at Berkeley (1996)
Morain, F.: Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques. Journal de Théorie des Nombres de Bordeaux 7(1), 111–138 (1995)
Morain, F.: Advances in the CM method for elliptic curves. In: Slides of Fields Cryptography Retrospective Meeting, May 11-15 (2009), http://www.lix.polytechnique.fr/~morain/Exposes/fields09.pdf
Schertz, R.: Weber’s class invariants revisited. Journal de Théorie des Nombres de Bordeaux 14(1), 325–343 (2002)
Shoup, V.: NTL: A library for doing number theory, 5.5 edn. (2008), http://www.shoup.net/ntl/
Sutherland, A.V.: Computing Hilbert class polynomials with the Chinese Remainder Theorem. Mathematics of Computation (to appear 2010), http://arxiv.org/abs/0903.2785
Weber, H.: Lehrbuch der Algebra, 3rd edn., vol. III. Chelsea, New York (1961)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Enge, A., Sutherland, A.V. (2010). Class Invariants by the CRT Method. In: Hanrot, G., Morain, F., Thomé, E. (eds) Algorithmic Number Theory. ANTS 2010. Lecture Notes in Computer Science, vol 6197. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14518-6_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-14518-6_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14517-9
Online ISBN: 978-3-642-14518-6
eBook Packages: Computer ScienceComputer Science (R0)