Constructing Elliptic Curves over Ramanujan's Class Invariants

Abstract:

The Complex Multiplication (CM) method is a widely used technique for constructing elliptic curves over finite fields. The key point in this method is parameter generation of the elliptic curve and root compution of a special type of class polynomials. However, there are several class polynomials which can be used in the CM method, having much smaller coefficients, and fulfilling the prerequisite that their roots can be easily transformed to the roots of the corresponding Hilbert polynomials.In this paper, we provide a method which can construct elliptic curves by Ramanujan's class invariants. We described the algorithm for the construction of elliptic curves (ECs) over imaginary quadratic field and given the transformation from their roots to the roots of the corresponding Hilbert polynomials. We compared the efficiency in the use of this method and other methods.

• Periodical: Advanced Materials Research (Volumes 915-916)
• Pages: 1336-1340
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.915-916.1336
• Online since: April 2014
• Authors: Jian Jun Hu
• Keywords: Class Polynomials, Complex Multiplication, Elliptic Curves, Imaginary Quadratic Field

References

[1] G. Frey, H.G. Rück, A remark concerning m-divisibility and the discrete logarithm problem in the divisor class group of curves, Mathematics of Computation 62 (1994) 865-874.

DOI: 10.1090/s0025-5718-1994-1218343-6

[2] A.J. Menezes, T. Okamoto, S.A. Vanstone, Reducing elliptic curve logarithms to a finite field, Institute of Electrical and Electronics Engineers. Transactions on Information Theory 39 (1993) 1639-1646.

DOI: 10.1109/18.259647

[3] G.C. Pohlig, M.E. Hellman, An improved algorithm for computing logarithms over GF. p/ and its cryptographic significance, Institute of Electrical and Electronics Engineers. Transactions on Information Theory 24 (1978) 106-110.

DOI: 10.1109/tit.1978.1055817

[4] T. Satoh, K. Araki, Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves, Commentarii Mathematici Universitatis Sancti Pauli 47 (1998) 81-91.

[5] A.O.L. Atkin, F. Morain, Elliptic curves and primality proving, Mathematics of Computation 61 (1993) 29-67.

DOI: 10.1090/s0025-5718-1993-1199989-x

[6] G.J. Lay, H. Zimmer, Constructing elliptic curves with given group order over large finite fields, in: Algorithmic Number Theory, ANTS-I, in: LNCS, vol. 877, Springer-Verlag, 1994, pp.250-263.

DOI: 10.1007/3-540-58691-1_64

[7] R. Schoof, Counting points on elliptic curves over finite fields, Journal de Theorie des Nombres de Bordeaux 7 (1995) 219-254.

DOI: 10.5802/jtnb.142

[8] R. Schertz, Weber's class invariants revisited, Journal de Théorie des Nombres de Bordeaux 4 (2002) 325-343.

DOI: 10.5802/jtnb.361

[9] Elisavet Konstantinou, Aristides Kontogeorgis, Ramanujan's class invariants and their use in elliptic curve cryptography, computers and mathmematics with applications, 59(2010)2901-2917.

DOI: 10.1016/j.camwa.2010.02.008

[10] E. Konstantinou, A. Kontogeorgis, Computing polynomials of the Ramanujan tn class invariants, Canadian Mathematical Bulletin 52 (4) (2009) 583-597.

DOI: 10.4153/cmb-2009-058-6

[11] S. Ramanujan, Notebooks. Vols. 1, 2, Tata Institute of Fundamental Research, Bombay, (1957).

[12] B.C. Berndt, H.H. Chan, Ramanujan and the modular j-invariant, Canadian Mathematical Bulletin 42 (4) (1999) 427-440.

DOI: 10.4153/cmb-1999-050-1

[13] A. Gee, Class invariants by Shimura's reciprocity law, Journal de Théorie des Nombres de Bordeaux 11 (1999) 45-72.

DOI: 10.5802/jtnb.238

[14] A. Gee, P. Stevenhagen, Generating class fields using Shimura reciprocity, in: Algorithmic Number Theory (Portland, OR, 1998), in: LNCS, vol. 1423, Springer-Verlag, 1998, pp.441-453.

DOI: 10.1007/bfb0054883

[15] William B. Hart, Schläfli modular equations for generalized Weber functions, Ramanujan J (2008) 15: 435–468.

DOI: 10.1007/s11139-007-9087-8