A 𝑝-adic algorithm to compute the Hilbert class polynomial

Bröker, Reinier

doi:10.1090/S0025-5718-08-02091-7

A $p$-adic algorithm to compute the Hilbert class polynomial
HTML articles powered by AMS MathViewer

by Reinier Bröker PDF

Math. Comp. 77 (2008), 2417-2435 Request permission

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(|\Delta |(\log |\Delta |)^{8+\varepsilon })$ instead of $O(|\Delta |^{1+\varepsilon })$. We illustrate the algorithm by computing the polynomial $P_{-639}$ using a $643$-adic algorithm.

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
R. Bröker, Constructing elliptic curves of prescribed order, Ph.D. thesis, Universiteit Leiden, 2006.
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
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
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
Fred Diamond and John Im, Modular forms and modular curves, Seminar on Fermat’s Last Theorem (Toronto, ON, 1993–1994) CMS Conf. Proc., vol. 17, Amer. Math. Soc., Providence, RI, 1995, pp. 39–133. MR 1357209
S. J. Edixhoven, Stable models of modular curves and applications, Ph.D. thesis, Universiteit Utrecht, 1989.
A. Enge, The complexity of class polynomial computation via floating point approximations, Preprint, 2006.
J. Franke, T. Kleinjung, F. Morain, and T. Wirth, Proving the primality of very large numbers with fastECPP, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, 2004, pp. 194–207. MR 2137354, DOI 10.1007/978-3-540-24847-7_{1}4
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167
G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, Oxford, at the Clarendon Press, 1954. 3rd ed. MR 0067125
D. Kohel, Endomorphism rings of elliptic curves over finite fields, Ph.D. thesis, University of California at Berkeley, 1996.
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
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
H. W. Lenstra Jr. and Carl Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), no. 3, 483–516. MR 1137100, DOI 10.1090/S0894-0347-1992-1137100-0
Hideyuki Matsumura, Commutative ring theory, Cambridge Studies in Advanced Mathematics, vol. 8, Cambridge University Press, Cambridge, 1986. Translated from the Japanese by M. Reid. MR 879273
Jürgen Neukirch, Algebraic number theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 322, Springer-Verlag, Berlin, 1999. Translated from the 1992 German original and with a note by Norbert Schappacher; With a foreword by G. Harder. MR 1697859, DOI 10.1007/978-3-662-03983-0
René Schoof, Counting points on elliptic curves over finite fields, J. Théor. Nombres Bordeaux 7 (1995), no. 1, 219–254. Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). MR 1413578
René Schoof, Nonsingular plane cubic curves over finite fields, J. Combin. Theory Ser. A 46 (1987), no. 2, 183–211. MR 914657, DOI 10.1016/0097-3165(87)90003-3
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
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, 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
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
J. Vélu, Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A–B 273 (1971), A238–A241.