×
Sutherland, Andrew V.

Constructing elliptic curves over finite fields with prescribed torsion. (English) Zbl 1267.11074

Math. Comput. 81, No. 278, 1131-1147 (2012).
Summary: We present a method for constructing optimized equations for the modular curve \( X_1(N)\) using a local search algorithm on a suitably defined graph of birationally equivalent plane curves. We then apply these equations over a finite field \( \mathbb F_q\) to efficiently generate elliptic curves with nontrivial \( N\)-torsion by searching for affine points on \( X_1(N)(\mathbb F_q)\), and we give a fast method for generating curves with (or without) a point of order \( 4N\) using \( X_1(2N)\).

Cited in 2 Reviews
Cited in 33 Documents

MSC:

11G05 Elliptic curves over global fields
11-04 Software, source code, etc. for problems pertaining to number theory
11G20 Curves over finite and local fields
14G15 Finite ground fields in algebraic geometry

Software:

OEIS
Cite Review PDF
Full Text: DOI arXiv

Online Encyclopedia of Integer Sequences:

Minimal degree of X_1(n).

References:

[1] A. O. L. Atkin and F. Morain, Finding suitable curves for the elliptic curve method of factorization, Math. Comp. 60 (1993), no. 201, 399 – 405. · Zbl 0815.11063
[2] Houria Baaziz, Equations for the modular curve \?\(_{1}\)(\?) and models of elliptic curves with torsion points, Math. Comp. 79 (2010), no. 272, 2371 – 2386. · Zbl 1252.11038
[3] Juliana Belding, Reinier Bröker, Andreas Enge, and Kristin Lauter, Computing Hilbert class polynomials, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 5011, Springer, Berlin, 2008, pp. 282 – 295. · Zbl 1205.11139 · doi:10.1007/978-3-540-79456-1_19
[4] Peter Caday and Andrew V. Sutherland, Optimized equations for \( X_1(N)\) via simulated annealing, 2010, poster presented at Algorithmic Number Theory Symposium-ANTS IX, http://ants9.org/slides/poster_caday.pdf.
[5] Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren , Handbook of elliptic and hyperelliptic curve cryptography, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006. · Zbl 1082.94001
[6] Andreas Enge and Andrew V. Sutherland, Class invariants for the CRT method, Algorithmic Number Theory Symposium-ANTS IX , Lecture Notes in Computer Science, vol. 6197, Springer-Verlag, 2010, pp. 142-156. · Zbl 1260.11083
[7] Ernst-Ulrich Gekeler, The distribution of group structures on elliptic curves over finite prime fields, Doc. Math. 11 (2006), 119 – 142. · Zbl 1130.11054
[8] Benedict H. Gross, A tameness criterion for Galois representations associated to modular forms (mod \?), Duke Math. J. 61 (1990), no. 2, 445 – 517. · Zbl 0743.11030 · doi:10.1215/S0012-7094-90-06119-8
[9] Everett W. Howe, On the group orders of elliptic curves over finite fields, Compositio Math. 85 (1993), no. 2, 229 – 247. · Zbl 0793.14023
[10] Dale Husemoller, Elliptic curves, Graduate Texts in Mathematics, vol. 111, Springer-Verlag, New York, 1987. With an appendix by Ruth Lawrence. · Zbl 0605.14032
[11] Daeyeol Jeon, Chang Heon Kim, and Euisung Park, On the torsion of elliptic curves over quartic number fields, J. London Math. Soc. (2) 74 (2006), no. 1, 1 – 12. · Zbl 1165.11054 · doi:10.1112/S0024610706022940
[12] Daeyeol Jeon, Chang Heon Kim, and Andreas Schweizer, On the torsion of elliptic curves over cubic number fields, Acta Arith. 113 (2004), no. 3, 291 – 301. · Zbl 1083.11038 · doi:10.4064/aa113-3-6
[13] Daeyeol Jeon and Chang Heon Kim, On the arithmetic of certain modular curves, Acta Arith. 130 (2007), no. 2, 181 – 193. · Zbl 1134.11027 · doi:10.4064/aa130-2-7
[14] Daeyeol Jeon, Chang Heon Kim, and Yoonjin Lee, Families of elliptic curves over quartic number fields with prescribed torsion subgroups, Mathematics of Computation 80 (2011), 2395-2410. · Zbl 1267.11072
[15] Daeyeol Jeon, Chang Heon Kim, and Yoonjin Lee, Families of elliptic curves over cubic number fields with prescribed torsion subgroups, Math. Comp. 80 (2011), no. 273, 579 – 591. · Zbl 1214.11071
[16] S. Kamienny and B. Mazur, Rational torsion of prime order in elliptic curves over number fields, Astérisque 228 (1995), 3, 81 – 100. With an appendix by A. Granville; Columbia University Number Theory Seminar (New York, 1992). · Zbl 0846.14012
[17] Anthony W. Knapp, Elliptic curves, Mathematical Notes, vol. 40, Princeton University Press, Princeton, NJ, 1992. · Zbl 0804.14013
[18] Daniel Sion Kubert, Universal bounds on the torsion of elliptic curves, Proc. London Math. Soc. (3) 33 (1976), no. 2, 193 – 237. · Zbl 0331.14010 · doi:10.1112/plms/s3-33.2.193
[19] B. Mazur, Rational points on modular curves, Modular functions of one variable, V (Proc. Second Internat. Conf., Univ. Bonn, Bonn, 1976) Springer, Berlin, 1977, pp. 107 – 148. Lecture Notes in Math., Vol. 601.
[20] Loïc Merel, Bornes pour la torsion des courbes elliptiques sur les corps de nombres, Invent. Math. 124 (1996), no. 1-3, 437 – 449 (French). · Zbl 0936.11037 · doi:10.1007/s002220050059
[21] J. Miret, R. Moreno, A. Rio, and M. Valls, Determining the 2-Sylow subgroup of an elliptic curve over a finite field, Math. Comp. 74 (2005), no. 249, 411 – 427. · Zbl 1084.11032
[22] Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), no. 177, 243 – 264. · Zbl 0608.10005
[23] Pierre Parent, Bornes effectives pour la torsion des courbes elliptiques sur les corps de nombres, J. Reine Angew. Math. 506 (1999), 85 – 116 (French, with French summary). · Zbl 0919.11040 · doi:10.1515/crll.1999.009
[24] Markus A. Reichert, Explicit determination of nontrivial torsion structures of elliptic curves over quadratic number fields, Math. Comp. 46 (1986), no. 174, 637 – 658. · Zbl 0605.14028
[25] Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. · Zbl 0585.14026
[26] Neil J. A. Sloane, The on-line encyclopedia of integer sequences, 2010, published electronically at http://oeis.org. · Zbl 1159.11327
[27] Andrew V. Sutherland, Computing Hilbert class polynomials with the Chinese remainder theorem, Math. Comp. 80 (2011), no. 273, 501 – 538. · Zbl 1231.11144
[28] Richard G. Swan, Factorization of polynomials over finite fields, Pacific J. Math. 12 (1962), 1099 – 1106. · Zbl 0113.01701
[29] Yifan Yang, Defining equations of modular curves, Adv. Math. 204 (2006), no. 2, 481 – 508. · Zbl 1137.11027 · doi:10.1016/j.aim.2005.05.019
[30] Andrew Chi Chih Yao, On the evaluation of powers, SIAM J. Comput. 5 (1976), no. 1, 100 – 103. · Zbl 0326.68025 · doi:10.1137/0205008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.