2011, 5(1): 109-118. doi: 10.3934/amc.2011.5.109

Some remarks on the construction of class polynomials

1. 

Department of Information and Communication Systems Engineering, University of the Aegean, 83200, Samos, Greece

2. 

Department of Mathematics, University of Athens, Panepistimioupolis 15784, Athens, Greece

Received  September 2010 Revised  November 2010 Published  February 2011

Class invariants are singular values of modular functions which generate the class fields of imaginary quadratic number fields. Their minimal polynomials, called class polynomials, are uniquely determined by a discriminant $-D<0$ and are used in many applications, including the generation of elliptic curves. In all these applications, it is desirable that the size of the polynomials is as small as possible. Among all known class polynomials, Weber polynomials constructed with discriminants $-D \equiv 1$ (mod $8$) have the smallest height and require the least precision for their construction. In this paper, we will show that this fact does not necessarily lead to the most efficient computations, since the congruences modulo $8$ of the discriminants affect the degrees of the polynomials.
Citation: Elisavet Konstantinou, Aristides Kontogeorgis. Some remarks on the construction of class polynomials. Advances in Mathematics of Communications, 2011, 5 (1) : 109-118. doi: 10.3934/amc.2011.5.109
References:
[1]

L. V. Ahlfors, "Complex Analysis. An Introduction to the Theory of Analytic Functions of One Complex Variable,'', $3^{rd}$ edition, (1978).

[2]

J. Belding, R. Bröker, A. Enge and K. Lauter, Computing Hilbert class polynomials,, in, (2008), 282.

[3]

W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: the user language,, J. Symbolic Comput., 24 (1997), 235. doi: 10.1006/jsco.1996.0125.

[4]

R. Bröker, A $p$-adic algorithm to compute the Hilbert class polynomial,, Math. Compu., 77 (2008), 2417. doi: 10.1090/S0025-5718-08-02091-7.

[5]

A. Enge, The complexity of class polynomial computation via floating point approximations,, Math. Compu., 78 (2009), 1089. doi: 10.1090/S0025-5718-08-02200-X.

[6]

A. Enge and F. Morain, Comparing invariants for class fields of imaginary quadratic fields,, in, (2002), 252.

[7]

A. Enge and R. Schertz, Constructing elliptic curves over finite fields using double eta-quotients,, J. Théor. Nombres Bordeaux, 16 (2004), 555.

[8]

A. Enge and A. V. Sutherland, Class invariants for the CRT method,, in, (2010), 142.

[9]

E. Konstantinou and A. Kontogeorgis, Computing polynomials of the Ramanujan $t_n$ class invariants,, Canadian Math. Bull., 52 (2009), 583. doi: 10.4153/CMB-2009-058-6.

[10]

E. Konstantinou and A. Kontogeorgis, Ramanujan's class invariants and their use in elliptic curve cryptography,, Comput. Math. Appl., 59 (2010), 2901. doi: 10.1016/j.camwa.2010.02.008.

[11]

G. J. Lay and H. Zimmer, Constructing elliptic curves with given group order over large finite fields,, in, (1994), 250.

[12]

F. Morain, Modular curves and class invariants,, preprint., ().

[13]

F. Morain, Advances in the CM method for elliptic curves,, in, (2009).

[14]

W. Narkiewicz, "Elementary and Analytic Theory of Algebraic Numbers,'' $2^{nd}$ edition,, Springer-Verlag, (1990).

[15]

R. Schertz, Weber's class invariants revisited,, J. Théor. Nombres Bordeaux, 4 (2002), 325.

[16]

A. V. Sutherland, Computing Hilbert class polynomials with the Chinese Remainder Theorem,, Math. Compu., ().

show all references

References:
[1]

L. V. Ahlfors, "Complex Analysis. An Introduction to the Theory of Analytic Functions of One Complex Variable,'', $3^{rd}$ edition, (1978).

[2]

J. Belding, R. Bröker, A. Enge and K. Lauter, Computing Hilbert class polynomials,, in, (2008), 282.

[3]

W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: the user language,, J. Symbolic Comput., 24 (1997), 235. doi: 10.1006/jsco.1996.0125.

[4]

R. Bröker, A $p$-adic algorithm to compute the Hilbert class polynomial,, Math. Compu., 77 (2008), 2417. doi: 10.1090/S0025-5718-08-02091-7.

[5]

A. Enge, The complexity of class polynomial computation via floating point approximations,, Math. Compu., 78 (2009), 1089. doi: 10.1090/S0025-5718-08-02200-X.

[6]

A. Enge and F. Morain, Comparing invariants for class fields of imaginary quadratic fields,, in, (2002), 252.

[7]

A. Enge and R. Schertz, Constructing elliptic curves over finite fields using double eta-quotients,, J. Théor. Nombres Bordeaux, 16 (2004), 555.

[8]

A. Enge and A. V. Sutherland, Class invariants for the CRT method,, in, (2010), 142.

[9]

E. Konstantinou and A. Kontogeorgis, Computing polynomials of the Ramanujan $t_n$ class invariants,, Canadian Math. Bull., 52 (2009), 583. doi: 10.4153/CMB-2009-058-6.

[10]

E. Konstantinou and A. Kontogeorgis, Ramanujan's class invariants and their use in elliptic curve cryptography,, Comput. Math. Appl., 59 (2010), 2901. doi: 10.1016/j.camwa.2010.02.008.

[11]

G. J. Lay and H. Zimmer, Constructing elliptic curves with given group order over large finite fields,, in, (1994), 250.

[12]

F. Morain, Modular curves and class invariants,, preprint., ().

[13]

F. Morain, Advances in the CM method for elliptic curves,, in, (2009).

[14]

W. Narkiewicz, "Elementary and Analytic Theory of Algebraic Numbers,'' $2^{nd}$ edition,, Springer-Verlag, (1990).

[15]

R. Schertz, Weber's class invariants revisited,, J. Théor. Nombres Bordeaux, 4 (2002), 325.

[16]

A. V. Sutherland, Computing Hilbert class polynomials with the Chinese Remainder Theorem,, Math. Compu., ().

[1]

Simona Fornaro, Luca Lorenzi. Generation results for elliptic operators with unbounded diffusion coefficients in $L^p$- and $C_b$-spaces. Discrete & Continuous Dynamical Systems - A, 2007, 18 (4) : 747-772. doi: 10.3934/dcds.2007.18.747

[2]

Monica Lazzo. Existence and multiplicity results for a class of nonlinear elliptic problems in $\mathbb(R)^N$. Conference Publications, 2003, 2003 (Special) : 526-535. doi: 10.3934/proc.2003.2003.526

[3]

Patrick Winkert. Multiplicity results for a class of elliptic problems with nonlinear boundary condition. Communications on Pure & Applied Analysis, 2013, 12 (2) : 785-802. doi: 10.3934/cpaa.2013.12.785

[4]

Hongjie Dong, Doyoon Kim. Schauder estimates for a class of non-local elliptic equations. Discrete & Continuous Dynamical Systems - A, 2013, 33 (6) : 2319-2347. doi: 10.3934/dcds.2013.33.2319

[5]

Tommaso Leonori, Ireneo Peral, Ana Primo, Fernando Soria. Basic estimates for solutions of a class of nonlocal elliptic and parabolic equations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (12) : 6031-6068. doi: 10.3934/dcds.2015.35.6031

[6]

Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215-235. doi: 10.3934/amc.2010.4.215

[7]

Kazuhiko Yamamoto, Kiyoshi Hosono, Hiroko Nakayama, Akio Ito, Yuichi Yanagi. Experimental data for solid tumor cells: Proliferation curves and time-changes of heat shock proteins. Discrete & Continuous Dynamical Systems - S, 2012, 5 (1) : 235-244. doi: 10.3934/dcdss.2012.5.235

[8]

Nicholas Hoell, Guillaume Bal. Ray transforms on a conformal class of curves. Inverse Problems & Imaging, 2014, 8 (1) : 103-125. doi: 10.3934/ipi.2014.8.103

[9]

Philip N. J. Eagle, Steven D. Galbraith, John B. Ong. Point compression for Koblitz elliptic curves. Advances in Mathematics of Communications, 2011, 5 (1) : 1-10. doi: 10.3934/amc.2011.5.1

[10]

Alfonso Castro, Rosa Pardo. A priori estimates for positive solutions to subcritical elliptic problems in a class of non-convex regions. Discrete & Continuous Dynamical Systems - B, 2017, 22 (3) : 783-790. doi: 10.3934/dcdsb.2017038

[11]

Yaoping Chen, Jianqing Chen. Existence of multiple positive weak solutions and estimates for extremal values for a class of concave-convex elliptic problems with an inverse-square potential. Communications on Pure & Applied Analysis, 2017, 16 (5) : 1531-1552. doi: 10.3934/cpaa.2017073

[12]

Alice Silverberg. Some remarks on primality proving and elliptic curves. Advances in Mathematics of Communications, 2014, 8 (4) : 427-436. doi: 10.3934/amc.2014.8.427

[13]

David L. Finn. Convexity of level curves for solutions to semilinear elliptic equations. Communications on Pure & Applied Analysis, 2008, 7 (6) : 1335-1343. doi: 10.3934/cpaa.2008.7.1335

[14]

Paul H. Rabinowitz. On a class of reversible elliptic systems. Networks & Heterogeneous Media, 2012, 7 (4) : 927-939. doi: 10.3934/nhm.2012.7.927

[15]

Moises Delgado, Heeralal Janwa. Some new results on the conjecture on exceptional APN functions and absolutely irreducible polynomials: The gold case. Advances in Mathematics of Communications, 2017, 11 (2) : 389-396. doi: 10.3934/amc.2017033

[16]

Farman Mamedov, Sara Monsurrò, Maria Transirico. Potential estimates and applications to elliptic equations. Conference Publications, 2015, 2015 (special) : 793-800. doi: 10.3934/proc.2015.0793

[17]

Zainidin Eshkuvatov. Homotopy perturbation method and Chebyshev polynomials for solving a class of singular and hypersingular integral equations. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 337-350. doi: 10.3934/naco.2018022

[18]

Siegfried Carl. Comparison results for a class of quasilinear evolutionary hemivariational inequalities. Conference Publications, 2007, 2007 (Special) : 221-229. doi: 10.3934/proc.2007.2007.221

[19]

Joseph H. Silverman. Local-global aspects of (hyper)elliptic curves over (in)finite fields. Advances in Mathematics of Communications, 2010, 4 (2) : 101-114. doi: 10.3934/amc.2010.4.101

[20]

Ravi Vakil and Aleksey Zinger. A natural smooth compactification of the space of elliptic curves in projective space. Electronic Research Announcements, 2007, 13: 53-59.

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (44)
  • HTML views (0)
  • Cited by (1)

[Back to Top]