{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T08:34:18Z","timestamp":1776846858402,"version":"3.51.2"},"reference-count":43,"publisher":"American Mathematical Society (AMS)","issue":"266","license":[{"start":{"date-parts":[[2009,11,17]],"date-time":"2009-11-17T00:00:00Z","timestamp":1258416000000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n We analyse the complexity of computing class polynomials, that are an important ingredient for CM constructions of elliptic curves, via complex floating point approximations of their roots. The heart of the algorithm is the evaluation of modular functions in several arguments. The fastest one of the presented approaches uses a technique devised by Dupont to evaluate modular functions by Newton iterations on an expression involving the arithmetic-geometric mean. Under the heuristic assumption, justified by experiments, that the correctness of the result is not perturbed by rounding errors, the algorithm runs in time\n \n \\[\n \n \n \n O<\/mml:mi>\n \n (<\/mml:mo>\n \n \n |<\/mml:mo>\n <\/mml:mrow>\n D<\/mml:mi>\n \n |<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msqrt>\n \n log<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msup>\n \n \u2061\n \n <\/mml:mo>\n \n |<\/mml:mo>\n <\/mml:mrow>\n D<\/mml:mi>\n \n |<\/mml:mo>\n <\/mml:mrow>\n \n M<\/mml:mi>\n \n (<\/mml:mo>\n \n \n |<\/mml:mo>\n <\/mml:mrow>\n D<\/mml:mi>\n \n |<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msqrt>\n \n log<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n \u2061\n \n <\/mml:mo>\n \n |<\/mml:mo>\n <\/mml:mrow>\n D<\/mml:mi>\n \n |<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n \n \u2286\n \n <\/mml:mo>\n O<\/mml:mi>\n \n (<\/mml:mo>\n \n |<\/mml:mo>\n <\/mml:mrow>\n D<\/mml:mi>\n \n |<\/mml:mo>\n <\/mml:mrow>\n \n log<\/mml:mi>\n \n 6<\/mml:mn>\n +<\/mml:mo>\n \n \u03b5\n \n <\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n \n \u2061\n \n <\/mml:mo>\n \n |<\/mml:mo>\n <\/mml:mrow>\n D<\/mml:mi>\n \n |<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n \n \u2286\n \n <\/mml:mo>\n O<\/mml:mi>\n \n (<\/mml:mo>\n \n h<\/mml:mi>\n \n 2<\/mml:mn>\n +<\/mml:mo>\n \n \u03b5\n \n <\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n O \\left ( \\sqrt {|D|} \\log ^3 |D| \\, M \\left ( \\sqrt {|D|} \\log ^2 |D| \\right ) \\right ) \\subseteq O \\left (|D| \\log ^{6 + \\varepsilon } |D| \\right ) \\subseteq O \\left ( h^{2 + \\varepsilon } \\right )<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n \\]\n <\/disp-formula>\n for any\n \n \n \n \n \n \u03b5\n \n <\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n \\varepsilon > 0<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , where\n \n \n \n D<\/mml:mi>\n D<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is the CM discriminant,\n \n \n \n h<\/mml:mi>\n h<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is the degree of the class polynomial and\n \n \n \n \n M<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n M (n)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is the time needed to multiply two\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -bit numbers. Up to logarithmic factors, this running time matches the size of the constructed polynomials. The estimate also relies on a new result concerning the complexity of enumerating the class group of an imaginary quadratic order and on a rigorously proven upper bound for the height of class polynomials.\n <\/p>","DOI":"10.1090\/s0025-5718-08-02200-x","type":"journal-article","created":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T13:09:23Z","timestamp":1259672963000},"page":"1089-1107","source":"Crossref","is-referenced-by-count":38,"title":["The complexity of class polynomial computation via floating point approximations"],"prefix":"10.1090","volume":"78","author":[{"given":"Andreas","family":"Enge","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2008,11,17]]},"reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"Amod Agashe, Kristin Lauter, and Ramarathnam Venkatesan, Constructing elliptic curves with a known number of points over a prime field, High Primes and Misdemeanours: Lectures in Honour of the 60th Birthday of Hugh Cowie Williams (Alf van der Poorten and Andreas Stein, eds.), Fields Institute Communications, vol. 41, American Mathematical Society, 2004.","DOI":"10.1090\/fic\/041\/01"},{"issue":"246","key":"2","doi-asserted-by":"publisher","first-page":"1023","DOI":"10.1090\/S0025-5718-03-01501-1","article-title":"Prime sieves using binary quadratic forms","volume":"73","author":"Atkin, A. O. L.","year":"2004","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"203","key":"3","doi-asserted-by":"publisher","first-page":"29","DOI":"10.2307\/2152935","article-title":"Elliptic curves and primality proving","volume":"61","author":"Atkin, A. O. L.","year":"1993","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"191","key":"4","doi-asserted-by":"publisher","first-page":"355","DOI":"10.2307\/2008811","article-title":"Explicit bounds for primality testing and related problems","volume":"55","author":"Bach, Eric","year":"1990","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"5","doi-asserted-by":"crossref","unstructured":"Paulo S. L. M. Barreto, Ben Lynn, and Michael Scott, Constructing elliptic curves with prescribed embedding degrees, Security in Communication Networks \u2014 Third International Conference, SCN 2002, Amalfi, Italy, September 2002 (Berlin) (Stelvio Cimato, Clemente Galdi, and Giuseppe Persiano, eds.), Lecture Notes in Computer Science, vol. 2576, Springer-Verlag, 2003, pp. 257\u2013267.","DOI":"10.1007\/3-540-36413-7_19"},{"issue":"2","key":"6","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1145\/321941.321944","article-title":"Fast multiple-precision evaluation of elementary functions","volume":"23","author":"Brent, Richard P.","year":"1976","journal-title":"J. Assoc. Comput. Mach.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"issue":"1","key":"7","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s10623-004-3808-4","article-title":"Elliptic curves suitable for pairing based cryptography","volume":"37","author":"Brezing, Friederike","year":"2005","journal-title":"Des. Codes Cryptogr.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-1022","issn-type":"print"},{"issue":"4","key":"8","first-page":"255","article-title":"Effective lower and upper bounds for the Fourier coefficients of powers of the modular invariant \ud835\udc57","volume":"20","author":"Brisebarre, Nicolas","year":"2005","journal-title":"J. Ramanujan Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0970-1249","issn-type":"print"},{"key":"9","unstructured":"Reinier Br\u00f6ker, Constructing elliptic curves of prescribed order, Proefschrift, Universiteit Leiden, 2006."},{"key":"10","isbn-type":"print","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-540-24847-7_8","article-title":"Elliptic curves with a given number of points","author":"Br\u00f6ker, Reinier","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/3540221565"},{"key":"11","unstructured":"Michele Cipolla, Un metodo per la risoluzione della congruenza di secondo grado, Napoli Rend. 9 (1903), 153\u2013163."},{"key":"12","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02945-9","volume-title":"A course in computational algebraic number theory","volume":"138","author":"Cohen, Henri","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540556400"},{"key":"13","isbn-type":"print","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/3-540-45455-1_19","article-title":"Action of modular correspondences around CM points","author":"Couveignes, Jean-Marc","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/3540438637"},{"key":"14","series-title":"A Wiley-Interscience Publication","isbn-type":"print","volume-title":"Primes of the form $x^2 + ny^2$","author":"Cox, David A.","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/0471506540"},{"key":"15","unstructured":"R. Dedekind, Erl\u00e4uterungen zu den vorstehenden Fragmenten, Bernhard Riemann\u2019s gesammelte mathematische Werke und wissenschaftlicher Nachla\u00df (R. Dedekind and H. Weber, eds.), Teubner, Leipzig, 1876, pp. 438\u2013447."},{"key":"16","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/BF02940746","article-title":"Die Typen der Multiplikatorenringe elliptischer Funktionenk\u00f6rper","volume":"14","author":"Deuring, Max","year":"1941","journal-title":"Abh. Math. Sem. Hansischen Univ.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5858","issn-type":"print"},{"key":"17","series-title":"Enzyklop\\\"{a}die der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen, Band I 2, Heft 10, Teil I","volume-title":"Die Klassenk\\\"{o}rper der komplexen Multiplikation","author":"Deuring, M.","year":"1958"},{"key":"18","unstructured":"R\u00e9gis Dupont, Fast evaluation of modular functions using Newton iterations and the AGM, To appear in Mathematics of Computation, \\url{http:\/\/www.lix.polytechnique.fr\/Labo\/Regis.Dupont\/preprints\/Dupont_{F}astEvalMod.ps.gz}, 2007."},{"issue":"2","key":"19","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s00145-004-0219-7","article-title":"Building curves with arbitrary small MOV degree over finite prime fields","volume":"18","author":"Dupont, R\u00e9gis","year":"2005","journal-title":"J. Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"key":"20","unstructured":"Andreas Enge, mpfrcx \u2014 a library for univariate polynomials over arbitrary precision real or complex numbers, Version 0.1, \\url{http:\/\/www.lix.polytechnique.fr\/Labo\/Andreas.Enge\/Software.html}."},{"key":"21","isbn-type":"print","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/3-540-45455-1_21","article-title":"Comparing invariants for class fields of imaginary quadratric fields","author":"Enge, Andreas","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/3540438637"},{"key":"22","unstructured":"\\bysame, Further investigations of the generalised Weber functions, In preparation, 2007."},{"issue":"3","key":"23","doi-asserted-by":"publisher","first-page":"555","DOI":"10.5802\/jtnb.460","article-title":"Constructing elliptic curves over finite fields using double eta-quotients","volume":"16","author":"Enge, Andreas","year":"2004","journal-title":"J. Th\\'{e}or. Nombres Bordeaux","ISSN":"https:\/\/id.crossref.org\/issn\/1246-7405","issn-type":"print"},{"key":"24","unstructured":"Andreas Enge and Paul Zimmermann, mpc \u2014 a library for multiprecision complex arithmetic with exact rounding, Version 0.4.6, \\url{http:\/\/www.lix.polytechnique.fr\/Labo\/Andreas.Enge\/Software.html}."},{"key":"25","unstructured":"Leonhard Euler, Evolutio producti infiniti (1-\ud835\udc65)(1-\ud835\udc65\ud835\udc65)(1-\ud835\udc65\u00b3)(1-\ud835\udc65\u2074)(1-\ud835\udc65\u2075)(1-\ud835\udc65\u2076) etc. in seriem simplicem, Acta academiae scientiarum Petropolitanae 1780:I (1783), 125\u2013169, Opera Omnia I.3:472\u2013479."},{"key":"26","doi-asserted-by":"crossref","unstructured":"Martin F\u00fcrer, Faster integer multiplication, Proceedings of the 39th Annual ACM Symposium on Theory of Computing \u2014 STOC\u201907 (New York) (Association for Computing Machinery, ed.), ACM, 2007, pp. 57\u201366.","DOI":"10.1145\/1250790.1250800"},{"key":"27","isbn-type":"print","volume-title":"Modern computer algebra","author":"von zur Gathen, Joachim","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/0521641764"},{"issue":"3","key":"28","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BF01272074","article-title":"Computing Frobenius maps and factoring polynomials","volume":"2","author":"von zur Gathen, Joachim","year":"1992","journal-title":"Comput. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/1016-3328","issn-type":"print"},{"key":"29","unstructured":"Pierrick Gaudry, Assembly support for GMP on AMD64, April 2005, \\url{http:\/\/www.loria.fr\/ gaudry\/mpn_{A}MD64\/}."},{"issue":"1","key":"30","doi-asserted-by":"publisher","first-page":"45","DOI":"10.5802\/jtnb.238","article-title":"Class invariants by Shimura\u2019s reciprocity law","volume":"11","author":"Gee, Alice","year":"1999","journal-title":"J. Th\\'{e}or. Nombres Bordeaux","ISSN":"https:\/\/id.crossref.org\/issn\/1246-7405","issn-type":"print"},{"key":"31","isbn-type":"print","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/BFb0054883","article-title":"Generating class fields using Shimura reciprocity","author":"Gee, Alice","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/3540646574"},{"key":"32","unstructured":"Torbj\u00f6rn Granlund et al., gmp \u2014 GNU multiprecision library, Version 4.2.1, \\url{http:\/\/gmplib.org\/}."},{"key":"33","unstructured":"Guillaume Hanrot, Vincent Lef\u00e8vre, Patrick P\u00e9lissier, and Paul Zimmermann et al., mpfr \u2014 a library for multiple-precision floating-point computations with exact rounding, Version 2.2.1, \\url{http:\/\/www.mpfr.org}."},{"key":"34","isbn-type":"print","first-page":"673","article-title":"Algorithms in number theory","author":"Lenstra, A. K.","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0444880712"},{"key":"35","unstructured":"R. Lercier and E. Riboulet-Deyris, Elliptic curves with complex multiplication, Posting to Number Theory List, \\url{http:\/\/listserv.nodak.edu\/cgi-bin\/wa.exe?A2=ind0401&L=nmbrthry&P=R305}, 2004."},{"key":"36","unstructured":"Atsuko Miyaji, Masaki Nakabayashi, and Shunzou Takano, New explicit conditions of elliptic curve traces for FR-reduction, IEICE Trans. Fundamentals E84-A (2001), no. 5, 1234\u20131243."},{"key":"37","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1515\/crll.1976.286-287.46","article-title":"Die singul\u00e4ren Werte der Weberschen Funktionen \ud835\udd23,\ud835\udd23\ud835\udd30\ud835\udd1f1,\ud835\udd23\u2082, \ud835\udefe\u2082, \ud835\udefe\u2083","volume":"286(287)","author":"Schertz, Reinhard","year":"1976","journal-title":"J. Reine Angew. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0075-4102","issn-type":"print"},{"issue":"1","key":"38","doi-asserted-by":"publisher","first-page":"325","DOI":"10.5802\/jtnb.361","article-title":"Weber\u2019s class invariants revisited","volume":"14","author":"Schertz, Reinhard","year":"2002","journal-title":"J. Th\\'{e}or. Nombres Bordeaux","ISSN":"https:\/\/id.crossref.org\/issn\/1246-7405","issn-type":"print"},{"key":"39","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/bf02242355","article-title":"Schnelle Multiplikation grosser Zahlen","volume":"7","author":"Sch\u00f6nhage, A.","year":"1971","journal-title":"Computing (Arch. Elektron. Rechnen)","ISSN":"https:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"key":"40","doi-asserted-by":"crossref","unstructured":"Arnold Sch\u00f6nhage, Fast reduction and composition of binary quadratic forms, Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation \u2014 ISSAC \u201991 (Stephen M. Watt, ed.), ACM Press, 1991, pp. 128\u2013133.","DOI":"10.1145\/120694.120711"},{"key":"41","isbn-type":"print","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/978-1-4612-0457-2_15","article-title":"The exponents of the groups of points on the reductions of an elliptic curve","author":"Schoof, Ren\u00e9","year":"1991","ISBN":"https:\/\/id.crossref.org\/isbn\/0817635130"},{"key":"42","doi-asserted-by":"crossref","unstructured":"Carl Ludwig Siegel, \u00dcber die Classenzahl quadratischer Zahlk\u00f6rper, Acta Arithmetica 1 (1936), 83\u201386.","DOI":"10.4064\/aa-1-1-83-86"},{"key":"43","unstructured":"Heinrich Weber, Lehrbuch der Algebra, 2nd ed., vol. 3: Elliptische Funktionen und algebraische Zahlen, Vieweg, Braunschweig, 1908."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2009-78-266\/S0025-5718-08-02200-X\/S0025-5718-08-02200-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2009-78-266\/S0025-5718-08-02200-X\/S0025-5718-08-02200-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:58:13Z","timestamp":1776787093000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2009-78-266\/S0025-5718-08-02200-X\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11,17]]},"references-count":43,"journal-issue":{"issue":"266","published-print":{"date-parts":[[2009,4]]}},"alternative-id":["S0025-5718-08-02200-X"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-08-02200-x","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2008,11,17]]}}}