Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

A $ p$-adic algorithm to compute the Hilbert class polynomial


Author: Reinier Bröker
Journal: Math. Comp. 77 (2008), 2417-2435
MSC (2000): Primary 11G15
DOI: https://doi.org/10.1090/S0025-5718-08-02091-7
Published electronically: April 23, 2008
MathSciNet review: 2429891
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Classically, the Hilbert class polynomial $ P_{\Delta }\in \mathbf{Z} [X]$ of an imaginary quadratic discriminant $ \Delta $ is computed using complex analytic techniques. In 2002, Couveignes and Henocq suggested a $ p$-adic algorithm to compute $ P_{\Delta }$. Unlike the complex analytic method, it does not suffer from problems caused by rounding errors. In this paper we give a detailed description of the algorithm in the paper by Couveignes and Henocq, and our careful study of the complexity shows that, if the Generalized Riemann Hypothesis holds true, the expected runtime of the $ p$-adic algorithm is $ O(\vert\Delta \vert(\log \vert\Delta \vert)^{8+\varepsilon })$ instead of $ O(\vert\Delta \vert^{1+\varepsilon })$. We illustrate the algorithm by computing the polynomial $ P_{-639}$ using a $ 643$-adic algorithm.


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

  • 1. A. Agashe, K. Lauter, R. 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 H. C. Williams, Fields Institute Communications Series, vol. 41, 2004, pp. 1-17. MR 2075643 (2005m:11112)
  • 2. R. Bröker, Constructing elliptic curves of prescribed order, Ph.D. thesis, Universiteit Leiden, 2006.
  • 3. H. Cohen, A course in computational algebraic number theory, Springer Graduate Texts in Mathematics, vol. 138, 1993. MR 1228206 (94i:11105)
  • 4. H. Cohen, G. Frey et al., Handbook of elliptic and hyperelliptic curve cryptography, Chapman & Hall, 2006. MR 2162716 (2007f:14020)
  • 5. J.-M. Couveignes, T. Henocq, Action of modular correspondences around CM-points, Algorithmic Number Theory Symposium V, Springer Lecture Notes in Computer Science, vol. 2369, 2002, pp. 234-243. MR 2041087 (2005b:11077)
  • 6. F. Diamond, J. Im, Modular forms and modular curves, Seminar on Fermat's last theorem, CMS conference proceedings, vol. 17, 1995, pp. 39-133. MR 1357209 (97g:11044)
  • 7. S. J. Edixhoven, Stable models of modular curves and applications, Ph.D. thesis, Universiteit Utrecht, 1989.
  • 8. A. Enge, The complexity of class polynomial computation via floating point approximations, Preprint, 2006.
  • 9. J. Franke, T. Kleinjung, F. Morain, T. Wirth, Proving the primality of very large numbers with fastECPP, Algorithmic Number Theory Symposium VI, Springer Lecture Notes in Computer Science, vol. 3076, 2004, pp. 194-207. MR 2137354 (2006a:11172)
  • 10. J. von zur Gathen, J. Gerhard, Modern computer algebra, Cambridge University Press, 1999. MR 1689167 (2000j:68205)
  • 11. G. H. Hardy, E. M. Wright, An introduction to the theory of numbers, Oxford University Press, 1938. MR 0067125 (16:673c)
  • 12. D. Kohel, Endomorphism rings of elliptic curves over finite fields, Ph.D. thesis, University of California at Berkeley, 1996.
  • 13. J. C. Lagarias, A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic Number Fields, ed. A. Fröhlich, Academic Press, 1977, pp. 409-465. MR 0447191 (56:5506)
  • 14. S. Lang, Elliptic functions, Springer Graduate Texts in Mathematics, vol. 112, 1987. MR 890960 (88c:11028)
  • 15. H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), 649-673. MR 916721 (89g:11125)
  • 16. H. W. Lenstra, Jr., C. Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), 483-516. MR 1137100 (92m:11145)
  • 17. H. Matsumura, Commutative ring theory, Cambridge Studies in Advanced Mathematics, vol. 8, 1986. MR 879273 (88h:13001)
  • 18. J. Neukirch, Algebraic number theory, Springer, Grundlehren der mathematischen Wissenschaften, vol. 322, 1999. MR 1697859 (2000m:11104)
  • 19. R. Schoof, Counting points on elliptic curves over finite fields, J. Théor. Nombres Bordeaux 7 (1993), 219-254. MR 1413578 (97i:11070)
  • 20. R. Schoof, Nonsingular plane cubic curves over finite fields, J. Combin. Theory Ser. A 46 (1987), 183-211. MR 914657 (88k:14013)
  • 21. R. Schoof, The exponents of the groups of points of the reductions of an elliptic curve, Arithmetic Algebraic Geometry, ed. G. van der Geer, 1991. MR 1085266 (91j:11043)
  • 22. J.-P. Serre, Complex multiplication, Algebraic Number Theory, ed. J. W. S. Cassels & A. Fröhlich, Academic Press, 1967. MR 0244199 (39:5516)
  • 23. J. H. Silverman, Advanced topics in the arithmetic of elliptic curves, Springer Graduate Texts in Mathematics, vol. 151, 1994. MR 1312368 (96b:11074)
  • 24. J. H. Silverman, The arithmetic of elliptic curves, Springer Gruadate Texts in Mathematics, vol. 106, 1986. MR 817210 (87g:11070)
  • 25. J. Vélu, Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A-B 273 (1971), A238-A241.

Similar Articles

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

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


Additional Information

Reinier Bröker
Affiliation: Department of Mathematics and Statistics, University of Calgary, 2500 University Drive NW, Calgary, AB T2N 1N4, Canada
Address at time of publication: Microsoft Research, One Microsoft Way, Redmond, Washington 98052
Email: reinier@math.leidenuniv.nl

DOI: https://doi.org/10.1090/S0025-5718-08-02091-7
Received by editor(s): November 10, 2006
Received by editor(s) in revised form: June 27, 2007
Published electronically: April 23, 2008
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society