Computing Hilbert class polynomials with the Chinese remainder theorem

Sutherland, Andrew

doi:10.1090/S0025-5718-2010-02373-7

Computing Hilbert class polynomials with the Chinese remainder theorem
HTML articles powered by AMS MathViewer

by Andrew V. Sutherland PDF

Math. Comp. 80 (2011), 501-538

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(|D|^{1/2+\epsilon }\log {P})$ space and has an expected running time of $O(|D|^{1+\epsilon })$. We describe practical optimizations that allow us to handle larger discriminants than other methods, with $|D|$ 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

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, Fields Inst. Commun., vol. 41, Amer. Math. Soc., Providence, RI, 2004, pp. 1–17. MR 2075643
A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), no. 203, 29–68. MR 1199989, DOI 10.1090/S0025-5718-1993-1199989-X
A. O. L. Atkin and F. Morain, Finding suitable curves for the elliptic curve method of factorization, Math. Comp. 60 (1993), no. 201, 399–405. MR 1140645, DOI 10.1090/S0025-5718-1993-1140645-1
Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355–380. MR 1023756, DOI 10.1090/S0025-5718-1990-1023756-8
Juliana Belding, Reinier Bröker, Andreas Enge, and Kristin Lauter, Computing Hilbert class polynomials, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 5011, Springer, Berlin, 2008, pp. 282–295. MR 2467854, DOI 10.1007/978-3-540-79456-1_{1}9
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.
—, 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.
Daniel J. Bernstein and Jonathan P. Sorenson, Modular exponentiation via the explicit Chinese remainder theorem, Math. Comp. 76 (2007), no. 257, 443–454. MR 2261030, DOI 10.1090/S0025-5718-06-01849-7
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.
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.
I. F. Blake, G. Seroussi, and N. P. Smart, Elliptic curves in cryptography, London Mathematical Society Lecture Note Series, vol. 265, Cambridge University Press, Cambridge, 2000. Reprint of the 1999 original. MR 1771549
Reinier Bröker, A $p$-adic algorithm to compute the Hilbert class polynomial, Math. Comp. 77 (2008), no. 264, 2417–2435. MR 2429891, DOI 10.1090/S0025-5718-08-02091-7
Reinier Bröker and Peter Stevenhagen, Efficient CM-constructions of elliptic curves over finite fields, Math. Comp. 76 (2007), no. 260, 2161–2179. MR 2336289, DOI 10.1090/S0025-5718-07-01980-1
Johannes Buchmann and Arthur Schmidt, Computing the structure of a finite abelian group, Math. Comp. 74 (2005), no. 252, 2017–2026. MR 2164109, DOI 10.1090/S0025-5718-05-01740-0
Johannes Buchmann and Ulrich Vollmer, Binary quadratic forms, Algorithms and Computation in Mathematics, vol. 20, Springer, Berlin, 2007. An algorithmic approach. MR 2300780
Frank Celler and C. R. Leedham-Green, Calculating the order of an invertible matrix, Groups and computation, II (New Brunswick, NJ, 1995) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 28, Amer. Math. Soc., Providence, RI, 1997, pp. 55–60. MR 1444130
Jinhui Chao, Osamu Nakamura, Kohji Sobataka, and Shigeo Tsujii, Construction of secure elliptic cryptosystems using CM tests and liftings, Advances in cryptology—ASIACRYPT’98 (Beijing), Lecture Notes in Comput. Sci., vol. 1514, Springer, Berlin, 1998, pp. 95–109. MR 1727916, DOI 10.1007/3-540-49649-1_{9}
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
—, High precision computation of Hardy-Littlewood constants, 1999, available at http://www.math.u-bordeaux.fr/~cohen/hardylw.dvi.
Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren (eds.), Handbook of elliptic and hyperelliptic curve cryptography, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006. MR 2162716
Paula Cohen, On the coefficients of the transformation polynomials for the elliptic modular function, Math. Proc. Cambridge Philos. Soc. 95 (1984), no. 3, 389–402. MR 755826, DOI 10.1017/S0305004100061697
Jean-Marc Couveignes and Thierry Henocq, Action of modular correspondences around CM points, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 234–243. MR 2041087, DOI 10.1007/3-540-45455-1_{1}9
David A. Cox, Primes of the form $x^2 + ny^2$, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1989. Fermat, class field theory and complex multiplication. MR 1028322
Richard Crandall and Carl Pomerance, Prime numbers, 2nd ed., Springer, New York, 2005. A computational perspective. MR 2156291
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.
Max Deuring, Die Typen der Multiplikatorenringe elliptischer Funktionenkörper, Abh. Math. Sem. Hansischen Univ. 14 (1941), 197–272 (German). MR 5125, DOI 10.1007/BF02940746
Andreas Enge, The complexity of class polynomial computation via floating point approximations, Math. Comp. 78 (2009), no. 266, 1089–1107. MR 2476572, DOI 10.1090/S0025-5718-08-02200-X
Andreas Enge, Computing modular polynomials in quasi-linear time, Math. Comp. 78 (2009), no. 267, 1809–1824. MR 2501077, DOI 10.1090/S0025-5718-09-02199-1
Mireille Fouquet and François Morain, Isogeny volcanoes and the SEA algorithm, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 276–291. MR 2041091, DOI 10.1007/3-540-45455-1_{2}3
David Freeman, Constructing pairing-friendly elliptic curves with embedding degree 10, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 4076, Springer, Berlin, 2006, pp. 452–465. MR 2282942, DOI 10.1007/11792086_{3}2
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.
Ernst-Ulrich Gekeler, The distribution of group structures on elliptic curves over finite prime fields, Doc. Math. 11 (2006), 119–142. MR 2226271
Torbjörn Granlund et al., GNU multiple precision arithmetic library, September 2008, version 4.2.4, available at http://gmplib.org/.
James L. Hafner and Kevin S. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. 2 (1989), no. 4, 837–850. MR 1002631, DOI 10.1090/S0894-0347-1989-1002631-0
David Harvey, Faster polynomial multiplication via multipoint Kronecker substitution, J. Symbolic Comput. 44 (2009), no. 10, 1502–1510. MR 2543433, DOI 10.1016/j.jsc.2009.05.004
—, $\text {zn\_poly}$: A library for polynomial arithmetic, 2008, version 0.9, http://cims.nyu. edu/~harvey/zn_poly.
Derek F. Holt, Bettina Eick, and Eamonn A. O’Brien, Handbook of computational group theory, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2005. MR 2129747, DOI 10.1201/9781420035216
Everett W. Howe, On the group orders of elliptic curves over finite fields, Compositio Math. 85 (1993), no. 2, 229–247. MR 1204781
Dale Husemoller, Elliptic curves, Graduate Texts in Mathematics, vol. 111, Springer-Verlag, New York, 1987. With an appendix by Ruth Lawrence. MR 868861, DOI 10.1007/978-1-4757-5119-2
Michael J. Jacobson Jr., Shantha Ramachandran, and Hugh C. Williams, Numerical results on class groups of imaginary quadratic fields, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 4076, Springer, Berlin, 2006, pp. 87–101. MR 2282917, DOI 10.1007/11792086_{7}
—, 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.
Daeyeol Joen and Chang Heon Kim, On the arithmetic of certain modular curves, 2006, http://arxiv.org/abs/math/0607611v1.
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.
Koray Karabina and Edlyn Teske, On prime-order elliptic curves with embedding degrees $k=3$, $4$, and $6$, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 5011, Springer, Berlin, 2008, pp. 102–117. MR 2467839, DOI 10.1007/978-3-540-79456-1_{6}
Kiran S. Kedlaya and Andrew V. Sutherland, Computing $L$-series of hyperelliptic curves, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 5011, Springer, Berlin, 2008, pp. 312–326. MR 2467855, DOI 10.1007/978-3-540-79456-1_{2}1
David Kohel, Endomorphism rings of elliptic curves over finite fields, Ph.D. thesis, University of California at Berkeley, 1996.
Daniel Sion Kubert, Universal bounds on the torsion of elliptic curves, Proc. London Math. Soc. (3) 33 (1976), no. 2, 193–237. MR 434947, DOI 10.1112/plms/s3-33.2.193
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, Durham, 1975) Academic Press, London, 1977, pp. 409–464. MR 0447191
Serge Lang, Elliptic functions, 2nd ed., Graduate Texts in Mathematics, vol. 112, Springer-Verlag, New York, 1987. With an appendix by J. Tate. MR 890960, DOI 10.1007/978-1-4612-4752-4
Georg-Johann Lay and Horst G. Zimmer, Constructing elliptic curves with given group order over large finite fields, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 250–263. MR 1322728, DOI 10.1007/3-540-58691-1_{6}4
H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI 10.2307/1971363
J. E. Littlewood, On the class-number of the corpus ${P}(\sqrt {-k})$, Proceedings of the London Mathematical Society 27 (1928), 358–372.
J. Miret, R. Moreno, A. Rio, and M. Valls, Determining the 2-Sylow subgroup of an elliptic curve over a finite field, Math. Comp. 74 (2005), no. 249, 411–427. MR 2085900, DOI 10.1090/S0025-5718-04-01640-0
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, Appl. Math. Comput. 196 (2008), no. 1, 67–76. MR 2382590, DOI 10.1016/j.amc.2007.05.037
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
K. Rubin and A. Silverberg, Choosing the correct elliptic curve in the CM method, Math. Comp. 79 (2010), no. 269, 545–561. MR 2552240, DOI 10.1090/S0025-5718-09-02266-2
A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
René Schoof, The exponents of the groups of points on the reductions of an elliptic curve, Arithmetic algebraic geometry (Texel, 1989) Progr. Math., vol. 89, Birkhäuser Boston, Boston, MA, 1991, pp. 325–335. MR 1085266, DOI 10.1007/978-1-4612-0457-2_{1}5
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.
J.-P. Serre, Complex multiplication, Algebraic Number Theory (Proc. Instructional Conf., Brighton, 1965) Thompson, Washington, D.C., 1967, pp. 292–296. MR 0244199
Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR 817210, DOI 10.1007/978-1-4757-1920-8
Joseph H. Silverman, Advanced topics in the arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 151, Springer-Verlag, New York, 1994. MR 1312368, DOI 10.1007/978-1-4612-0851-8
Richard Stallman et al., GNU compiler collection, August 2008, version 4.3.2, available at http://gcc.gnu.org/.
Andrew V. Sutherland, Order computations in generic groups, Ph.D. thesis, MIT, 2007, http://groups.csail.mit.edu/cis/theses/sutherland-phd.pdf.
—, Constructing elliptic curves over finite fields with prescribed torsion, 2008, http://arxiv.org/abs/0811.0296.
—, Discrete logarithms and structure computation in finite abelian $p$-groups, Mathematics of Computation (2009), to appear, http://arxiv.org/abs/0809.3413.
Edlyn Teske, A space efficient algorithm for group structure computation, Math. Comp. 67 (1998), no. 224, 1637–1663. MR 1474658, DOI 10.1090/S0025-5718-98-00968-5
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.
Ulrich Vollmer, Invariant and discrete logarithm computation in quadratic orders, Ph.D. thesis, Technische Universität Darmstadt, 2003.
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
Lawrence C. Washington, Elliptic curves, 2nd ed., Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2008. Number theory and cryptography. MR 2404461, DOI 10.1201/9781420071474