Some remarks on the construction of class polynomials

Previous Article
Linear nonbinary covering codes and saturating sets in projective spaces
AMC Home
This Issue
Next Article
Codes from incidence matrices and line graphs of Paley graphs

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

Abstract
Related Papers

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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[12]	F. Morain, Modular curves and class invariants,, preprint., ().
[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
[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-343.
[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, McGraw-Hill Book Co., New York, 1978.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[12]	F. Morain, Modular curves and class invariants,, preprint., ().
[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
[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-343.
[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 and Continuous Dynamical Systems, 2007, 18 (4) : 747-772. doi: 10.3934/dcds.2007.18.747
[2]	Guilin Ji, Changjian Liu. The cyclicity of a class of quadratic reversible centers defining elliptic curves. Discrete and Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021299
[3]	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
[4]	Patrick Winkert. Multiplicity results for a class of elliptic problems with nonlinear boundary condition. Communications on Pure and Applied Analysis, 2013, 12 (2) : 785-802. doi: 10.3934/cpaa.2013.12.785
[5]	Hongjie Dong, Doyoon Kim. Schauder estimates for a class of non-local elliptic equations. Discrete and Continuous Dynamical Systems, 2013, 33 (6) : 2319-2347. doi: 10.3934/dcds.2013.33.2319
[6]	Tommaso Leonori, Ireneo Peral, Ana Primo, Fernando Soria. Basic estimates for solutions of a class of nonlocal elliptic and parabolic equations. Discrete and Continuous Dynamical Systems, 2015, 35 (12) : 6031-6068. doi: 10.3934/dcds.2015.35.6031
[7]	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
[8]	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 and Continuous Dynamical Systems - S, 2012, 5 (1) : 235-244. doi: 10.3934/dcdss.2012.5.235
[9]	Nicholas Hoell, Guillaume Bal. Ray transforms on a conformal class of curves. Inverse Problems and Imaging, 2014, 8 (1) : 103-125. doi: 10.3934/ipi.2014.8.103
[10]	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
[11]	Alfonso Castro, Rosa Pardo. A priori estimates for positive solutions to subcritical elliptic problems in a class of non-convex regions. Discrete and Continuous Dynamical Systems - B, 2017, 22 (3) : 783-790. doi: 10.3934/dcdsb.2017038
[12]	Agnid Banerjee, Ramesh Manna. Carleman estimates for a class of variable coefficient degenerate elliptic operators with applications to unique continuation. Discrete and Continuous Dynamical Systems, 2021, 41 (11) : 5105-5139. doi: 10.3934/dcds.2021070
[13]	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
[14]	David L. Finn. Convexity of level curves for solutions to semilinear elliptic equations. Communications on Pure and Applied Analysis, 2008, 7 (6) : 1335-1343. doi: 10.3934/cpaa.2008.7.1335
[15]	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 and Applied Analysis, 2017, 16 (5) : 1531-1552. doi: 10.3934/cpaa.2017073
[16]	Paul H. Rabinowitz. On a class of reversible elliptic systems. Networks and Heterogeneous Media, 2012, 7 (4) : 927-939. doi: 10.3934/nhm.2012.7.927
[17]	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
[18]	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
[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.

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Elisavet Konstantinou Aristides Kontogeorgis
on Google Scholar
Elisavet Konstantinou Aristides Kontogeorgis

[Back to Top]