Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

   
 
 

 

The complexity of class polynomial computation via floating point approximations


Author: Andreas Enge
Journal: Math. Comp. 78 (2009), 1089-1107
MSC (2000): Primary 11Y16; Secondary 11G15
DOI: https://doi.org/10.1090/S0025-5718-08-02200-X
Published electronically: November 17, 2008
MathSciNet review: 2476572
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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

$\displaystyle O \left( \sqrt {\vert D\vert} \log^3 \vert D\vert \, M \left( \sq... ...arepsilon} \vert D\vert \right) \subseteq O \left( h^{2 + \varepsilon} \right) $

for any $ \varepsilon > 0$, where $ D$ is the CM discriminant, $ h$ is the degree of the class polynomial and $ M (n)$ is the time needed to multiply two $ 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.


References [Enhancements On Off] (What's this?)

  • 1. 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. MR 2075643 (2005m:11112)
  • 2. A. O. L. Atkin and D. J. Bernstein, Prime sieves using binary quadratic forms, Mathematics of Computation 73 (2004), no. 246, 1023-1030. MR 2031423 (2004i:11147)
  • 3. A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Mathematics of Computation 61 (1993), no. 203, 29-68. MR 1199989 (93m:11136)
  • 4. Eric Bach, Explicit bounds for primality testing and related problems, Mathematics of Computation 55 (1990), no. 191, 355-380. MR 1023756 (91m:11096)
  • 5. Paulo S. L. M. Barreto, Ben Lynn, and Michael Scott, Constructing elliptic curves with prescribed embedding degrees, Security in Communication Networks -- 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-267.
  • 6. Richard P. Brent, Fast multiple-precision evaluation of elementary functions, Journal of the ACM 23 (1976), no. 2, 242-251. MR 0395314 (52:16111)
  • 7. Friederike Brezing and Annegret Weng, Elliptic curves suitable for pairing based cryptography, Designs, Codes and Cryptography 37 (2005), no. 1, 133-141. MR 2165045 (2006e:14029)
  • 8. N. Brisebarre and G. Philibert, Effective lower and upper bounds for the Fourier coefficients of powers of the modular invariant $ j$, Journal of the Ramanujan Mathematical Society 20 (2005), 255-282. MR 2193216 (2006k:11074)
  • 9. Reinier Bröker, Constructing elliptic curves of prescribed order, Proefschrift, Universiteit Leiden, 2006.
  • 10. Reinier Bröker and Peter Stevenhagen, Elliptic curves with a given number of points, Algorithmic Number Theory -- ANTS-VI (Berlin) (Duncan Buell, ed.), Lecture Notes in Computer Science, vol. 3076, Springer-Verlag, 2004, pp. 117-131. MR 2137348 (2005m:11113)
  • 11. Michele Cipolla, Un metodo per la risoluzione della congruenza di secondo grado, Napoli Rend. 9 (1903), 153-163.
  • 12. Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, Springer-Verlag, New York, 1993. MR 1228206 (94i:11105)
  • 13. Jean-Marc Couveignes and Thierry Henocq, Action of modular correspondences around CM points, Algorithmic Number Theory -- ANTS-V (Berlin) (Claus Fieker and David R. Kohel, eds.), Lecture Notes in Computer Science, vol. 2369, Springer-Verlag, 2002, pp. 234-243. MR 2041087 (2005b:11077)
  • 14. 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. MR 1028322 (90m:11016)
  • 15. R. Dedekind, Erläuterungen zu den vorstehenden Fragmenten, Bernhard Riemann's gesammelte mathematische Werke und wissenschaftlicher Nachlaß (R. Dedekind and H. Weber, eds.), Teubner, Leipzig, 1876, pp. 438-447.
  • 16. Max Deuring, Die Typen der Multiplikatorenringe elliptischer Funktionenkörper, Abhandlungen aus dem mathematischen Seminar der hamburgischen Universität 14 (1941), 197-272. MR 0005125 (3:104f)
  • 17. -, Die Klassenkörper der komplexen Multiplikation, Enzyklop. d. math. Wissenschaften, vol. I 2 Heft 10, Teubner, Stuttgart, 2e ed., 1958. MR 0167481 (29:4754)
  • 18. Régis Dupont, Fast evaluation of modular functions using Newton iterations and the AGM, To appear in Mathematics of Computation, http://www.lix.polytechnique.fr/Labo/Regis.Dupont/preprints/Dupont_FastEvalMod.ps.gz, 2007.
  • 19. Régis Dupont, Andreas Enge, and François Morain, Building curves with arbitrary small MOV degree over finite prime fields, Journal of Cryptology 18 (2005), no. 2, 79-89. MR 2148052 (2006c:11073)
  • 20. Andreas Enge, mpfrcx -- a library for univariate polynomials over arbitrary precision real or complex numbers, Version 0.1, http://www.lix.polytechnique.fr/Labo/Andreas.Enge/Software.html.
  • 21. Andreas Enge and François Morain, Comparing invariants for class fields of imaginary quadratic fields, Algorithmic Number Theory -- ANTS-V (Berlin) (Claus Fieker and David R. Kohel, eds.), Lecture Notes in Computer Science, vol. 2369, Springer-Verlag, 2002, pp. 252-266. MR 2041089 (2005a:11179)
  • 22. -, Further investigations of the generalised Weber functions, In preparation, 2007.
  • 23. Andreas Enge and Reinhard Schertz, Constructing elliptic curves over finite fields using double eta-quotients, Journal de Théorie des Nombres de Bordeaux 16 (2004), 555-568. MR 2144957 (2006d:11063)
  • 24. Andreas Enge and Paul Zimmermann, mpc -- a library for multiprecision complex arithmetic with exact rounding, Version 0.4.6, http://www.lix.polytechnique.fr/Labo/Andreas.Enge/Software.html.
  • 25. Leonhard Euler, Evolutio producti infiniti $ (1 - x)(1 - xx)(1 - x^3) (1 - x^4)(1 - x^5)(1 - x^6)$ etc. in seriem simplicem, Acta academiae scientiarum Petropolitanae 1780:I (1783), 125-169, Opera Omnia I.3:472-479.
  • 26. Martin Fürer, Faster integer multiplication, Proceedings of the 39th Annual ACM Symposium on Theory of Computing -- STOC'07 (New York) (Association for Computing Machinery, ed.), ACM, 2007, pp. 57-66.
  • 27. Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, 1999. MR 1689167 (2000j:68205)
  • 28. Joachim von zur Gathen and Victor Shoup, Computing Frobenius maps and factoring polynomials, Computational Complexity 2 (1992), 187-224. MR 1220071 (94d:12011)
  • 29. Pierrick Gaudry, Assembly support for GMP on AMD64, April 2005, http://www.loria.fr/~gaudry/mpn_AMD64/.
  • 30. Alice Gee, Class invariants by Shimura's reciprocity law, Journal de Théorie des Nombres de Bordeaux 11 (1999), no. 1, 45-72. MR 1730432 (2000i:11171)
  • 31. Alice Gee and Peter Stevenhagen, Generating class fields using Shimura reciprocity, Algorithmic Number Theory -- ANTS-III (Berlin) (J. P. Buhler, ed.), Lecture Notes in Computer Science, vol. 1423, Springer-Verlag, 1998, pp. 441-453. MR 1726092 (2000m:11112)
  • 32. Torbjörn Granlund et al., gmp -- GNU multiprecision library, Version 4.2.1, http://gmplib.org/.
  • 33. Guillaume Hanrot, Vincent Lefèvre, Patrick Pélissier, and Paul Zimmermann et al., mpfr -- a library for multiple-precision floating-point computations with exact rounding, Version 2.2.1, http://www.mpfr.org.
  • 34. A. K. Lenstra and H. W. Lenstra Jr., Algorithms in number theory, Algorithms and Complexity (Jan van Leeuwen, ed.), Handbook of Theoretical Computer Science, vol. A, Elsevier, Amsterdam, 1990, pp. 673-715. MR 1127178
  • 35. R. Lercier and E. Riboulet-Deyris, Elliptic curves with complex multiplication, Posting to Number Theory List, http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0401&L=nmbrthry&P=R305, 2004.
  • 36. 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-1243.
  • 37. Reinhard Schertz, Die singulären Werte der Weberschen Funktionen $ \mathfrak{f}$, $ \mathfrak{f}_1$, $ \mathfrak{f}_2$, $ \gamma_2$, $ \gamma_3$, Journal für die reine und angewandte Mathematik 286/287 (1976), 46-74. MR 0422213 (54:10205)
  • 38. -, Weber's class invariants revisited, Journal de Théorie des Nombres de Bordeaux 14 (2002), no. 1, 325-343. MR 1926005 (2003j:11139)
  • 39. A. Schönhage and V. Strassen, Schnelle Multiplikation großer Zahlen, Computing 7 (1971), 281-292. MR 0292344 (45:1431)
  • 40. Arnold Schönhage, Fast reduction and composition of binary quadratic forms, Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation -- ISSAC '91 (Stephen M. Watt, ed.), ACM Press, 1991, pp. 128-133.
  • 41. René Schoof, The exponents of the groups of points on the reductions of an elliptic curve, Arithmetic Algebraic Geometry (Boston) (G. van der Geer, F. Oort, and J. Steenbrink, eds.), Birkhaüser, 1991, pp. 325-335. MR 1085266 (91j:11043)
  • 42. Carl Ludwig Siegel, Über die Classenzahl quadratischer Zahlkörper, Acta Arithmetica 1 (1936), 83-86.
  • 43. Heinrich Weber, Lehrbuch der Algebra, 2nd ed., vol. 3: Elliptische Funktionen und algebraische Zahlen, Vieweg, Braunschweig, 1908.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16, 11G15

Retrieve articles in all journals with MSC (2000): 11Y16, 11G15


Additional Information

Andreas Enge
Affiliation: INRIA Saclay–Île-de-France & Laboratoire d’Informatique (CNRS/UMR 7161), École polytechnique, 91128 Palaiseau Cedex, France
Email: enge@lix.polytechnique.fr

DOI: https://doi.org/10.1090/S0025-5718-08-02200-X
Received by editor(s): April 24, 2007
Received by editor(s) in revised form: May 6, 2008
Published electronically: November 17, 2008
Article copyright: © Copyright 2008 by Andreas Enge

American Mathematical Society