American Institute of Mathematical Sciences

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

Some remarks on the construction of class polynomials

Elisavet Konstantinou 1, and  Aristides Kontogeorgis 2,

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.
Keywords: generation of elliptic curves., precision estimates, Class polynomials, experimental results.
Mathematics Subject Classification: Primary: 11R29; Secondary: 94A60, 11T7.
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, McGraw-Hill Book Co., New York, 1978.  Google Scholar

[2]

J. Belding, R. Bröker, A. Enge and K. Lauter, Computing Hilbert class polynomials, in "Algorithmic Number Theory Symposium - ANTS 2008,'' Springer-Verlag, (2008), 282-295.  Google Scholar

[3]

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

[4]

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

[5]

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

[6]

A. Enge and F. Morain, Comparing invariants for class fields of imaginary quadratic fields, in "Algorithmic Number Theory Symposium - ANTS 2002,'' Springer-Verlag, (2002), 252-266.  Google Scholar

[7]

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

[8]

A. Enge and A. V. Sutherland, Class invariants for the CRT method, in "Algorithmic Number Theory Symposium - ANTS 2010,'' Springer-Verlag, (2010), 142-156. Google Scholar

[9]

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

[10]

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

[11]

G. J. Lay and H. Zimmer, Constructing elliptic curves with given group order over large finite fields, in "Algorithmic Number Theory - ANTS-I,'' Springer-Verlag, (1994), 250-263.  Google Scholar

[12]

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

[13]

F. Morain, Advances in the CM method for elliptic curves, in "Slides of Fields Cryptography Retrospective Meeting,'' (2009); available online at http://www.lix.polytechnique.fr/~morain/Exposes/fields09.pdf Google Scholar

[14]

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

[15]

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

[16]

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

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, McGraw-Hill Book Co., New York, 1978.  Google Scholar

[2]

J. Belding, R. Bröker, A. Enge and K. Lauter, Computing Hilbert class polynomials, in "Algorithmic Number Theory Symposium - ANTS 2008,'' Springer-Verlag, (2008), 282-295.  Google Scholar

[3]

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

[4]

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

[5]

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

[6]

A. Enge and F. Morain, Comparing invariants for class fields of imaginary quadratic fields, in "Algorithmic Number Theory Symposium - ANTS 2002,'' Springer-Verlag, (2002), 252-266.  Google Scholar

[7]

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

[8]

A. Enge and A. V. Sutherland, Class invariants for the CRT method, in "Algorithmic Number Theory Symposium - ANTS 2010,'' Springer-Verlag, (2010), 142-156. Google Scholar

[9]

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

[10]

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

[11]

G. J. Lay and H. Zimmer, Constructing elliptic curves with given group order over large finite fields, in "Algorithmic Number Theory - ANTS-I,'' Springer-Verlag, (1994), 250-263.  Google Scholar

[12]

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

[13]

F. Morain, Advances in the CM method for elliptic curves, in "Slides of Fields Cryptography Retrospective Meeting,'' (2009); available online at http://www.lix.polytechnique.fr/~morain/Exposes/fields09.pdf Google Scholar

[14]

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

[15]

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

[16]

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

[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, 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, 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, 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]

Agnid Banerjee, Ramesh Manna. Carleman estimates for a class of variable coefficient degenerate elliptic operators with applications to unique continuation. Discrete & Continuous Dynamical Systems, 2021, 41 (11) : 5105-5139. doi: 10.3934/dcds.2021070
[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]

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
[15]

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
[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]

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
[18]

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
[19]

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.

[20]

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

2020 Impact Factor: 0.935

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy