Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

   
 
 

 

Computing Hilbert class polynomials with the Chinese remainder theorem


Author: Andrew V. Sutherland
Journal: Math. Comp. 80 (2011), 501-538
MSC (2010): Primary 11Y16; Secondary 11G15, 11G20, 14H52
DOI: https://doi.org/10.1090/S0025-5718-2010-02373-7
Published electronically: May 17, 2010
MathSciNet review: 2728992
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a space-efficient algorithm to compute the Hilbert class polynomial $ H_D(X)$ modulo a positive integer $ P$, based on an explicit form of the Chinese Remainder Theorem. Under the Generalized Riemann Hypothesis, the algorithm uses $ O(\vert D\vert^{1/2+\epsilon}\log{P})$ space and has an expected running time of $ O(\vert D\vert^{1+\epsilon})$. We describe practical optimizations that allow us to handle larger discriminants than other methods, with $ \vert D\vert$ as large as $ 10^{13}$ and $ h(D)$ up to $ 10^{6}$. We apply these results to construct pairing-friendly elliptic curves of prime order, using the CM method.


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

  • 1. Amod Agashe, Kristin Lauter, and Ramaranthnam 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 (A. J. van der Poorten and A. Stein, eds.), Fields Institute Communications, vol. 41, AMS, 2004, pp. 1-17. MR 2075643 (2005m:11112)
  • 2. A.O.L. Atkin and François Morain, Elliptic curves and primality proving, Mathematics of Computation 61 (1993), 29-68. MR 1199989 (93m:11136)
  • 3. -, Finding suitable curves for the elliptic curve method of factorization, Mathematics of Computation 60 (1993), 399-405. MR 1140645 (93k:11115)
  • 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. Juliana Belding, Reinier Bröker, Andreas Enge, and Kristin Lauter, Computing Hilbert class polynomials, Algorithmic Number Theory Symposium-ANTS VIII (A. J. van der Poorten and A. Stein, eds.), Lecture Notes in Computer Science, vol. 5011, Springer, 2008, pp. 282-295. MR 2467854 (2009j:11200)
  • 6. Daniel J. Bernstein, Detecting perfect powers in essentially linear time, and other studies in computational number theory, Ph.D. thesis, University of California at Berkeley, 1995.
  • 7. -, Multidigit modular multiplication with the explicit Chinese remainder theorem, 1995, Chapter 4 of the author's Ph.D. thesis, available at http://cr.yp.to/papers.html#mmecrt.
  • 8. -, Modular exponentiation via the explicit Chinese Remainder Theorem, Mathematics of Computation 76 (2007), 443-454. MR 2261030 (2007f:11142)
  • 9. Ingrid Biehl and Johannes Buchmann, An analysis of the reduction algorithms for binary quadratic forms, Voronoi's Impact on Modern Science (P. Engel and H. Syta, eds.), Institute of Mathematics, Kyiv, 1998, available at http://www.cdc.informatik.tu-darmstadt.de/reports/TR/TI-97-26.ps.gz, pp. 71-98.
  • 10. Gaetan Bisson and Andrew V. Sutherland, 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.
  • 11. Ian Blake, Gadiel Seroussi, and Nigel Smart, Elliptic curves in cryptography, London Mathematical Society Lecture Note Series, vol. 265, Cambridge University Press, 1999. MR 1771549 (2001i:94048)
  • 12. Reinier Bröker, A $ p$-adic algorithm to compute the Hilbert class polynomial, Mathematics of Computation 77 (2008), 2417-2435. MR 2429891 (2009j:11093)
  • 13. Reinier Bröker and Peter Stevenhagen, Efficient CM-constructions of elliptic curves over finite fields, Mathematics of Computation 76 (2007), 2161-2179. MR 2336289 (2008i:11077)
  • 14. Johannes Buchmann and Arthur Schmidt, Computing the structure of a finite abelian group, Mathematics of Computation 74 (2005), 2017-2026. MR 2164109 (2006c:20108)
  • 15. Johannes Buchmann and Ulrich Vollmer, Binary quadratic forms: An algorithmic approach, Algorithms and Computations in Mathematics, vol. 20, Springer, 2007. MR 2300780 (2008b:11046)
  • 16. Frank Celler and C. R. Leedham-Green, Calculating the order of an invertible matrix, Groups and Computation II, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 28, American Mathematical Society, 1997, pp. 55-60. MR 1444130 (98g:20001)
  • 17. Jinhui Chao, Osamu Nakamura, Kohji Sobataka, and Shigeo Tsujii, Construction of secure elliptic cryptosystems using CM tests and liftings, Advances in Cryptology-ASIACRYPT'98, Lecture Notes in Computer Science, vol. 1514, Springer, 1998, pp. 95-109. MR 1727916
  • 18. Henri Cohen, A course in computational algebraic number theory, Springer, 1996. MR 1228206 (94i:11105)
  • 19. -, High precision computation of Hardy-Littlewood constants, 1999, available at http://www.math.u-bordeaux.fr/~cohen/hardylw.dvi.
  • 20. Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren, Handbook of elliptic and hyperelliptic curve cryptography, Chapman and Hall, 2006. MR 2162716 (2007f:14020)
  • 21. Paula Cohen, On the coefficients of the transformation polynomials for the elliptic modular function, Math. Proc. of the Cambridge Philosophical Society 95 (1984), 389-402. MR 755826 (85k:11020)
  • 22. Jean-Marc Couveignes and Thierry Henocq, Action of modular correspondences around CM points, Algorithmic Number Theory Symposium-ANTS V (C. Fieker and D. R. Kohel, eds.), Lecture Notes in Computer Science, vol. 2369, Springer-Verlag, 2002, pp. 234-243. MR 2041087 (2005b:11077)
  • 23. David A. Cox, Primes of the form $ x^2+ny^2$: Fermat, class field theory, and complex multiplication, John Wiley and Sons, 1989. MR 1028322 (90m:11016)
  • 24. Richard Crandall and Carl Pomerance, Prime numbers: A computational perspective, second ed., Springer, 2005. MR 2156291 (2006a:11005)
  • 25. John E. Cremona and Andrew V. Sutherland, On a theorem of Mestre and Schoof, Journal de Théorie des Nombres de Bordeaux (2009), to appear, http://arxiv.org/abs/0901.0120.
  • 26. Max Deuring, Die Typen der Multiplikatorenringe elliptischer Funktionenkörper, Abh. Math. Sem. Hansischen Univ. 14 (1941), 197-272. MR 0005125 (3:104f)
  • 27. Andreas Enge, The complexity of class polynomial computation via floating point approximations, Mathematics of Computation 78 (2009), 1089-1107. MR 2476572
  • 28. -, Computing modular polynomials in quasi-linear time, Mathematics of Computation 78 (2009), 1809-1824. MR 2501077
  • 29. Mireille Fouquet and François Morain, Isogeny volcanoes and the SEA algorithm, Algorithmic Number Theory Symposium-ANTS V (C. Fieker and D. R. Kohel, eds.), Lecture Notes in Computer Science, vol. 2369, Springer, 2002, pp. 276-291. MR 2041091 (2005c:11077)
  • 30. David Freeman, Constructing pairing-friendly elliptic curves with embedding degree $ 10$, Algorithmic Number Theory Symposium-ANTS VII (F. Hess, S. Pauli, and M. Pohst, eds.), Lecture Notes in Computer Science, vol. 4076, Springer, 2006, pp. 452-465. MR 2282942 (2008b:14042)
  • 31. David Freeman, Michael Scott, and Edlyn Teske, A taxonomy of pairing-friendly elliptic curves, Journal of Cryptology (2009), DOI: 10.1007/s00145-009-9048-z, to appear in print.
  • 32. Ernst-Ulrich Gekeler, The distribution of group structures on elliptic curves over finite prime fields, Documenta Mathematica 11 (2006), 119-142. MR 2226271 (2007b:11143)
  • 33. Torbjörn Granlund et al., GNU multiple precision arithmetic library, September 2008, version 4.2.4, available at http://gmplib.org/.
  • 34. James L. Hafner and Kevin S. McCurley, A rigorous subexponential algorithm for computation of class groups, Journal of the American Mathematical Society 2 (1989), no. 4, 837-850. MR 1002631 (91f:11090)
  • 35. David Harvey, Faster polynomial multiplication via multipoint Kronecker substitution, Journal of Symbolic Computation 44 (2009), no. 10, 1502-1510. MR 2543433
  • 36. -, $\text{zn\_poly}$: A library for polynomial arithmetic, 2008, version 0.9, http://cims.nyu. edu/~harvey/zn_poly.
  • 37. Derek F. Holt, Bettina Eick, and Eamonn A. O'Brien, Handbook of computational group theory, CRC Press, 2005. MR 2129747 (2006f:20001)
  • 38. Everett W. Howe, On the group orders of elliptic curves over finite fields, Compositio Mathematica 85 (1993), 229-247. MR 1204781 (94a:11089)
  • 39. Dale Husemöller, Elliptic curves, Springer-Verlag, 1987. MR 868861 (88h:11039)
  • 40. Michael J. Jacobson, Jr., S. Ramachandran, and Hugh C. Williams, Numerical results on class groups of imaginary quadratic fields, Algorithmic Number Theory Symposium-ANTS VII (F. Hess, S. Pauli, and M. Pohst, eds.), Lecture Notes in Computer Science, vol. 4076, Springer, 2006, pp. 87-101. MR 2282917 (2007j:11178)
  • 41. -, Supplementary tables for ``Numerical results on class groups of imaginary quadratic fields'', 2006, available at http://www.math.tu-berlin.de/~ kant/ants/Proceedings/ ramachandran-74/ramachandran-74-tables.pdf.
  • 42. Daeyeol Joen and Chang Heon Kim, On the arithmetic of certain modular curves, 2006, http://arxiv.org/abs/math/0607611v1.
  • 43. Ezekiel J. Kachisa, Edward F. Schaefer, and Michael Scott, Constructing brezingweng pairing friendly elliptic curves using elements in the cyclotomic field, Pairing-Based Cryptography-Pairing 2008, Lecture Notes in Computer Science, vol. 5209, Springer, 2008, p. 126135.
  • 44. Koray Karabina and Edlyn Teske, On prime-order elliptic curves with embedding degrees $ k=3,4$, and $ 6$, Algorithmic Number Theory Symposium-ANTS VIII (A. J. van der Poorten and A. Stein, eds.), Lecture Notes in Computer Science, vol. 5011, Springer, 2008, pp. 102-117. MR 2467839
  • 45. Kiran S. Kedlaya and Andrew V. Sutherland, Computing $ L$-series of hyperelliptic curves, Algorithmic Number Theory Symposium-ANTS VIII (A. J. van der Poorten and A. Stein, eds.), Lecture Notes in Computer Science, vol. 5011, Springer, 2008, pp. 312-326. MR 2467855
  • 46. David Kohel, Endomorphism rings of elliptic curves over finite fields, Ph.D. thesis, University of California at Berkeley, 1996.
  • 47. Daniel Sion Kubert, Universal bounds on the torsion of elliptic curves, Proceedings of the London Mathematical Society 33 (1976), 193-237. MR 0434947 (55:7910)
  • 48. J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: $ L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Duram, 1975), Academic Press, 1977, pp. 409-464. MR 0447191 (56:5506)
  • 49. Serge Lang, Elliptic functions, second ed., Springer-Verlag, 1987. MR 890960 (88c:11028)
  • 50. Georg-Johann Lay and Horst G. Zimmer, Constructing elliptic curves with given group order over large finite fields, Algorithmic Number Theory Symposium-ANTS I (L. M. Adleman and M.-D. Huang, eds.), Lecture Notes in Computer Science, vol. 877, 1994, pp. 250-263. MR 1322728 (96a:11054)
  • 51. Hendrik W. Lenstra, Jr., Factoring integers with elliptic curves, Annals of Mathematics 126 (1987), 649-673. MR 916721 (89g:11125)
  • 52. J. E. Littlewood, On the class-number of the corpus $ {P}(\sqrt{-k})$, Proceedings of the London Mathematical Society 27 (1928), 358-372.
  • 53. J. Miret, R. Moreno, A. Rio, and M. Valls, Determining the $ 2$-sylow subgroup of an elliptic curve over a finite field, Mathematics of Computation 74 (2004), no. 249, 411-427. MR 2085900 (2005d:11090)
  • 54. J. Miret, R. Moreno, D. Sadornil, J. Tena, and M. Valls, Computing the height of volcanoes of l-isogenies of elliptic curves over finite fields, Applied Mathematics and Computation 196 (2008), no. 1, 67-76. MR 2382590 (2008m:11122)
  • 55. J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois Journal of Mathematics 6 (1962), 64-94. MR 0137689 (25:1139)
  • 56. Karl Rubin and Alice Silverberg, Choosing the correct elliptic curve in the CM method, Mathematics of Computation 79 (2010), no. 269, 545-561. MR 2552240
  • 57. A. Schönhage and V. Strassen, Schnelle Multiplikation großer Zahlen, Computing 7 (1971), 281-292. MR 0292344 (45:1431)
  • 58. René Schoof, The exponents of the groups of points on reductions of an elliptic curve, Arithmetic Algebraic Geometry (G. van der Geer, F. Oort, and J. Steenbrink, eds.), Birkhäuser, 1991, pp. 325-335. MR 1085266 (91j:11043)
  • 59. I. Schur, Einige Bemerkungen zu der vorstehenden Arbeit des Herrn G. Polya: Über die Verteilung der quadratischen Reste und Nichtreste, Nachr. Kon. Ges. Wiss. Göttingen, Math.-phys. Kl. (1918), 30-36, in Gesammelte Abhandlungen, vol. II, pp. 239-245, Springer, 1973.
  • 60. Jean-Pierre Serre, Complex multiplication, Algebraic Number Theory (J.W.S. Cassels and A. Frölich, eds.), Academic Press, 1967. MR 0244199 (39:5516)
  • 61. Joseph H. Silverman, The arithmetic of elliptic curves, Springer, 1986. MR 817210 (87g:11070)
  • 62. -, Advanced topics in the arithmetic of elliptic curves, Springer, 1999. MR 1312368 (96b:11074)
  • 63. Richard Stallman et al., GNU compiler collection, August 2008, version 4.3.2, available at http://gcc.gnu.org/.
  • 64. Andrew V. Sutherland, Order computations in generic groups, Ph.D. thesis, MIT, 2007, http://groups.csail.mit.edu/cis/theses/sutherland-phd.pdf.
  • 65. -, Constructing elliptic curves over finite fields with prescribed torsion, 2008, http://arxiv.org/abs/0811.0296.
  • 66. -, Discrete logarithms and structure computation in finite abelian $ p$-groups, Mathematics of Computation (2009), to appear, http://arxiv.org/abs/0809.3413.
  • 67. Edlyn Teske, A space efficient algorithm for group structure computation, Mathematics of Computation 67 (1998), 1637-1663. MR 1474658 (99a:11146)
  • 68. Frederik Vercauteren, Pairings on elliptic curves, Identity-Based Cryptography (M. Joye and G. Neven, eds.), Cryptology and Information Security Series, vol. 2, IOS Press, 2008, pp. 13-30.
  • 69. Ulrich Vollmer, Invariant and discrete logarithm computation in quadratic orders, Ph.D. thesis, Technische Universität Darmstadt, 2003.
  • 70. Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, second ed., Cambridge University Press, 2003. MR 2001757 (2004g:68202)
  • 71. Lawrence C. Washington, Elliptic curves: Number theory and cryptography, second ed., CRC Press, 2008. MR 2404461 (2009b:11101)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16, 11G15, 11G20, 14H52

Retrieve articles in all journals with MSC (2010): 11Y16, 11G15, 11G20, 14H52


Additional Information

Andrew V. Sutherland
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Email: drew@math.mit.edu

DOI: https://doi.org/10.1090/S0025-5718-2010-02373-7
Received by editor(s): March 3, 2009
Received by editor(s) in revised form: September 10, 2009
Published electronically: May 17, 2010
Article copyright: © Copyright 2010 by the author

American Mathematical Society