Geodesic
Method for constructing elliptic curves using complex multiplication and its optimizations
Prikladnaâ diskretnaâ matematika, no. 3 (2011), pp. 17-54.

Voir la notice de l'article provenant de la source Math-Net.Ru

Elliptic curves over finite fields with predefined conditions on the order are practically constructed using the theory of complex multiplication. A stage with the longest calculations in this method reconstructs some polynomial with integer coefficients. We prove some theoretical results and give a detailed account of the method itself and show how one can use a divisor of the mentioned polynomial with coefficients in an extension of the rational number field.
Keywords: elliptic curves, finite fields, simultaneous approximations.
Mots-clés : complex multiplication 
@article{PDM_2011_3_a2,
     author = {E. A. Grechnikov},
     title = {Method for constructing elliptic curves using complex multiplication and its optimizations},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {17--54},
     publisher = {mathdoc},
     number = {3},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2011_3_a2/}
}
TY  - JOUR
AU  - E. A. Grechnikov
TI  - Method for constructing elliptic curves using complex multiplication and its optimizations
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2011
SP  - 17
EP  - 54
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2011_3_a2/
LA  - ru
ID  - PDM_2011_3_a2
ER  - 
%0 Journal Article
%A E. A. Grechnikov
%T Method for constructing elliptic curves using complex multiplication and its optimizations
%J Prikladnaâ diskretnaâ matematika
%D 2011
%P 17-54
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2011_3_a2/
%G ru
%F PDM_2011_3_a2
E. A. Grechnikov. Method for constructing elliptic curves using complex multiplication and its optimizations. Prikladnaâ diskretnaâ matematika, no. 3 (2011), pp. 17-54. http://geodesic.mathdoc.fr/item/PDM_2011_3_a2/

[1] Koblitz N., “Elliptic curve cryptosystems”, Math. Comput., 48 (1987), 203–209 | DOI | MR | Zbl

[2] Miller V. S., “Uses of elliptic curves in cryptography”, LNCS, 218, 1986, 417–426 | MR | Zbl

[3] Lenstra H. W., “Factoring integers with elliptic curves”, Ann. Math., 126 (1987), 649–673 | DOI | MR | Zbl

[4] Atkin A. O. L., Morain F., “Elliptic curves and primality proving”, Math. Comput., 61:203 (1993), 29–68 | DOI | MR | Zbl

[5] Cox D. A., Primes of the form $x^2+ny^2$, Wiley, New York, 1989 | MR | Zbl

[6] Weber H., Lehrbuch der Algebra, v. 3, 3rd edition, Chelsea Publishing Company, New York, 1908

[7] Silverman J. H., The Arithmetic of Elliptic Curves, Springer, 1986 | MR

[8] Leng S., Ellipticheskie funktsii, Nauka, M., 1984 | MR

[9] Aierlend K., Rouzen M., Klassicheskoe vvedenie v sovremennuyu teoriyu chisel, Mir, M., 1987 | MR

[10] Cornacchia G., “Su di un metodo per la risoluzione in numeri interi dell' equazione $\sum_{h=0}^nC_hx^{n-h}y^h=P$”, Giorn. Mat. Batt., 46 (1908), 33–90 | Zbl

[11] Baier H., Efficient algorithms for generating elliptic curves over finite fields suitable for use in cryptography, Department of Computer Science, Technical University of Darmstadt, 2002

[12] Konstantinou E., Kontogeorgis A., Stamatiou Y. C., Zaroliagis C. D., “On the Efficient Generation of Prime-Order Elliptic Curves”, J. Cryptol., 23:3 (2010), 477–503 | DOI | MR | Zbl

[13] Deuring M., “Die Typen der Multiplikatorenringe elliptischer Funktionenkörper”, Abh. Math. Sem. Hansischen Univ., 14 (1941), 197–272 | DOI | MR | Zbl

[14] Lay G.-J., Zimmer H. G., “Constructing elliptic curves with given group order over large finite fields”, LNCS, 877, 1994, 250–263 | MR | Zbl

[15] Von Schrutka L., “Ein Beweis für die Zerlegbarkeit der Primzahlen von der Form $6n+1$ in ein einfaches und ein dreifaches Quadrat”, J. Reine Ang. Math., 140 (1911), 252–265

[16] Jacobstahl E., “Über die Darstellung der Primzahlen der Form $4n+1$ als Summe zweier Quadrate”, J. Reine Ang. Math., 132 (1907), 238–245 | DOI

[17] Schertz R., “Weber's class invariants revisited”, J. Théor. Nombr. Bord., 14:1 (2002), 325–343 | DOI | MR | Zbl

[18] Enge A., Schertz R., “Constructing elliptic curves over finite fields using double eta-quotients”, J. Théor. Nombr. Bord., 16:3 (2004), 555–568 | DOI | MR | Zbl

[19] Cohn H., Introduction to the construction of class fields, Cambridge University Press, 1985 | MR

[20] Leng S., Algebraicheskie chisla, Mir, M., 1966 | MR

[21] Enge A., “The complexity of class polynomial computation via floating point approximations”, Math. Comput., 78:266 (2009), 1089–1107 | MR | Zbl

[22] Brisebarre N., Philibert G., “Effective lower and upper bounds for the Fourier coefficients of powers of the modular invariant $j$”, J. Raman. Math. Soc., 20 (2005), 255–282 | MR | Zbl

[23] Enge A., Morain F., “Comparing invariants for class fields of imaginary quadratic fields”, LNCS, 2369, 2002, 252–266 | MR | Zbl

[24] Brentjes A. J., Multi-dimensional continued fraction algorithms, Mathematisch Centrum, Amsterdam, 1981 | MR | Zbl

[25] Peck L. G., “Simultaneous rational approximations to algebraic numbers”, Bull. Amer. Math. Soc., 67 (1961), 197–201 | DOI | MR | Zbl

[26] Khinchin A. Ya., Tsepnye drobi, Nauka, M., 1978 | MR

[27] Venkov B. A., Elementarnaya teoriya chisel, ONTI NKTP SSSR, 1937

[28] Grechnikov E. A., Optimizatsiya metoda s kompleksnym umnozheniem postroeniya ellipticheskoi krivoi, Dep. v VINITI 21.06.11, No 305-V2011, MGU im. M. V. Lomonosova, M., 2011