A classification of ECM-friendly families of elliptic curves using modular curves

Barbulescu, Razvan; Shinde, Sudarshan

doi:10.1090/mcom/3697

A classification of ECM-friendly families of elliptic curves using modular curves
HTML articles powered by AMS MathViewer

by Razvan Barbulescu and Sudarshan Shinde HTML | PDF

Math. Comp. 91 (2022), 1405-1436 Request permission

Abstract:

In this work, we establish a link between the classification of ECM-friendly elliptic curves and Mazur’s program B, which consists in parameterizing all the families of elliptic curves with exceptional Galois image. Motivated by Barbulescu et al. [ANTS X–proceedings of the tenth algorithmic number theory symposium, Berkeley, CA, 2013], we say an elliptic curve is ECM-friendly if it does not have complex multiplication and if its Galois image is exceptional for some level. Building upon two recent works which treated the case of congruence subgroups of prime-power level which occur for infinitely many $j$-invariants, we prove that there are exactly 1525 families of rational elliptic curves with distinct Galois images which are cartesian products of subgroups of prime-power level. This makes a complete list of rational families of ECM-friendly elliptic curves with cartesian Galois images, out of which less than 23 were known in the literature. We furthermore refine a heuristic of Montgomery to compare these families and conclude that the best 4 families which can be put in $a=-1$ twisted Edwards’ form are new.

References

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. MR 1140645, DOI 10.1090/S0025-5718-1993-1140645-1
Shi Bai, Pierrick Gaudry, Alexander Kruppa, François Morain, Emmanuel Thomé, and Paul Zimmermann, Crible algébrique: Distribution, optimisation — number field sieve (cado-nfs). Available at https://gitlab.inria.fr/cado-nfs/cado-nfs.
R. Barbulescu, P. Gaudry, A. Guillevic, and F. Morain, Discrete logarithms in GF($p^2$) — 160 digits, 2014, Announcement available at the NMBRTHRY archives, Item 004706
Razvan Barbulescu, Pierrick Gaudry, Aurore Guillevic, and François Morain, Improving NFS for the discrete logarithm problem in non-prime finite fields, Advances in cryptology—EUROCRYPT 2015. Part I, Lecture Notes in Comput. Sci., vol. 9056, Springer, Heidelberg, 2015, pp. 129–155. MR 3344923, DOI 10.1007/978-3-662-46800-5_{6}
Razvan Barbulescu, Joppe W. Bos, Cyril Bouvier, Thorsten Kleinjung, and Peter L. Montgomery, Finding ECM-friendly curves through a study of Galois properties, ANTS X—Proceedings of the Tenth Algorithmic Number Theory Symposium, Open Book Ser., vol. 1, Math. Sci. Publ., Berkeley, CA, 2013, pp. 63–86. MR 3207408, DOI 10.2140/obs.2013.1.63
Razvan Barbulescu and Armand Lachand, Some mathematical remarks on the polynomial selection in NFS, Math. Comp. 86 (2017), no. 303, 397–418. MR 3557804, DOI 10.1090/mcom/3112
R. Barbulescu and S. Shinde, Online complement for “A classification of ECM-friendly families using modular curves”, 2019, https://razvanbarbulescu.pages.math.cnrs.fr/ECMfriendly/ECMfriendly.html.
Daniel J. Bernstein, Peter Birkner, Tanja Lange, and Christiane Peters, ECM using Edwards curves, Math. Comp. 82 (2013), no. 282, 1139–1179. MR 3008853, DOI 10.1090/S0025-5718-2012-02633-0
Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters, Twisted Edwards curves, Progress in cryptology—AFRICACRYPT 2008, Lecture Notes in Comput. Sci., vol. 5023, Springer, Berlin, 2008, pp. 389–405. MR 2482341, DOI 10.1007/978-3-540-68164-9_{2}6
D. J. Bernstein, Peter Birkner, and Tanja Lange, Starfish on strike, International Conference on Cryptology and Information Security in Latin America, 2010, pp. 61–80.
Daniel J. Bernstein, Chitchanok Chuengsatiansup, David Kohel, and Tanja Lange, Twisted Hessian curves, Progress in cryptology—LATINCRYPT 2015, Lecture Notes in Comput. Sci., vol. 9230, Springer, Cham, 2015, pp. 269–294. MR 3447379, DOI 10.1007/978-3-319-22174-8_{1}5
Cyril Bouvier and Laurent Imbert, Faster cofactorization with ECM using mixed representations, Public-key cryptography—PKC 2020. Part II, Lecture Notes in Comput. Sci., vol. 12111, Springer, Cham, [2020] ©2020, pp. 483–504. MR 4095402, DOI 10.1007/978-3-030-45388-6_{1}7
Éric Brier and Christophe Clavier, New families of ECM curves for Cunningham numbers, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 6197, Springer, Berlin, 2010, pp. 96–109. MR 2721415, DOI 10.1007/978-3-642-14518-6_{1}1
David A. Cox and Walter R. Parry, Genera of congruence subgroups in $\textbf {Q}$-quaternion algebras, J. Reine Angew. Math. 351 (1984), 66–112. MR 749678
J. E. Cremona, Classical invariants and 2-descent on elliptic curves, J. Symbolic Comput. 31 (2001), no. 1-2, 71–87. Computational algebra and number theory (Milwaukee, WI, 1996). MR 1806207, DOI 10.1006/jsco.1998.1004
Ernie Croot, Smooth numbers in short intervals, Int. J. Number Theory 3 (2007), no. 1, 159–169. MR 2310498, DOI 10.1142/S1793042107000833
C. J. Cummins and S. Pauli, Congruence subgroups of $\textrm {PSL}(2,{\Bbb Z})$ of genus less than or equal to 24, Experiment. Math. 12 (2003), no. 2, 243–255. MR 2016709, DOI 10.1080/10586458.2003.10504495
Harris B. Daniels and Enrique González-Jiménez, Serre’s constant of elliptic curves over the rationals, Exp. Math. (2019), 1–19.
H. B. Daniels, Á. Lozano-Robledo, and J. S. Morrow, Towards a classification of entanglements of Galois representations attached to elliptic curves, Preprint, arXiv:2105.02060, 2021.
H. B. Daniels and J. S. Morrow, A group theoretic perspective on entanglements of division fields, Preprint, arXiv:2008.09886, 2020.
Alexandre Gélin, Thorsten Kleinjung, and Arjen K. Lenstra, Parametrizations for families of ECM-friendly curves, ISSAC’17—Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2017, pp. 165–171. MR 3703683, DOI 10.1145/3087604.3087606
Henriette Heer, Gary McGuire, and Oisín Robinson, JKL-ECM: an implementation of ECM using Hessian curves, LMS J. Comput. Math. 19 (2016), no. suppl. A, 83–99. MR 3540948, DOI 10.1112/S1461157016000231
N. Jones and K. McMurdy, Elliptic curves with non-abelian entanglements, Preprint, arXiv:2008.09087, 2020.
Antoine Joux and Reynald Lercier, Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the Gaussian integer method, Math. Comp. 72 (2003), no. 242, 953–967. MR 1954978, DOI 10.1090/S0025-5718-02-01482-5
Taechan Kim and Razvan Barbulescu, Extended tower number field sieve: a new complexity for the medium prime case, Advances in cryptology—CRYPTO 2016. Part I, Lecture Notes in Comput. Sci., vol. 9814, Springer, Berlin, 2016, pp. 543–571. MR 3565295, DOI 10.1007/978-3-662-53018-4_{2}0
Daniel Sion Kubert, Universal bounds on the torsion of elliptic curves, Proc. London Math. Soc. (3) 33 (1976), no. 2, 193–237. MR 434947, DOI 10.1112/plms/s3-33.2.193
A. K. Lenstra, H. W. Lenstra Jr., M. S. Manasse, and J. M. Pollard, The number field sieve, The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer, Berlin, 1993, pp. 11–42. MR 1321219, DOI 10.1007/BFb0091537
H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI 10.2307/1971363
Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), no. 177, 243–264. MR 866113, DOI 10.1090/S0025-5718-1987-0866113-7
Peter Lawrence Montgomery, An FFT extension of the elliptic curve method of factorization, ProQuest LLC, Ann Arbor, MI, 1992. Thesis (Ph.D.)–University of California, Los Angeles. MR 2688742
Brian Antony Murphy, Polynomial selection for the number field sieve integer factorisation algorithm, Ph.D. Thesis, The Australian National University, 1999.
J. M. Pollard, The lattice sieve, The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer, Berlin, 1993, pp. 43–49. MR 1321220, DOI 10.1007/BFb0091538
Jeremy Rouse and David Zureick-Brown, Elliptic curves over $\Bbb Q$ and 2-adic images of Galois, Res. Number Theory 1 (2015), Paper No. 12, 34. MR 3500996, DOI 10.1007/s40993-015-0013-7
Jean-Pierre Serre, Propriétés galoisiennes des points d’ordre fini des courbes elliptiques, Invent. Math. 15 (1972), no. 4, 259–331 (French). MR 387283, DOI 10.1007/BF01405086
Modular functions of one variable. VI, Lecture Notes in Mathematics, Vol. 627, Springer-Verlag, Berlin-New York, 1977. Edited by J.-P. Serre and D. B. Zagier. MR 0469871
Goro Shimura, Introduction to the arithmetic theory of automorphic functions, Kanô Memorial Lectures, No. 1, Iwanami Shoten Publishers, Tokyo; Princeton University Press, Princeton, N.J., 1971. Publications of the Mathematical Society of Japan, No. 11. MR 0314766
Joseph H. Silverman, The arithmetic of elliptic curves, 2nd ed., Graduate Texts in Mathematics, vol. 106, Springer, Dordrecht, 2009. MR 2514094, DOI 10.1007/978-0-387-09494-6
Andrew V. Sutherland, Computing images of Galois representations attached to elliptic curves, Forum Math. Sigma 4 (2016), Paper No. e4, 79. MR 3482279, DOI 10.1017/fms.2015.33
Andrew V. Sutherland and David Zywina, Modular curves of prime-power level with infinitely many rational points, Algebra Number Theory 11 (2017), no. 5, 1199–1229. MR 3671434, DOI 10.2140/ant.2017.11.1199
Hiromi Suyama, Informal preliminary report (8), 1985. Letter to Richard P. Brent.
Mark van Hoeij, An algorithm for computing the Weierstrass normal form, Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation, 1995, pp. 90–95.
Mark van Hoeij, Rational parametrizations of algebraic curves using a canonical divisor, J. Symbolic Comput. 23 (1997), no. 2-3, 209–227. Parametric algebraic curves and applications (Albuquerque, NM, 1995). MR 1448695, DOI 10.1006/jsco.1996.0084
Mark van Hoeij, Jürgen Klüners, and Andrew Novocin, Generating subfields, J. Symbolic Comput. 52 (2013), 17–34. MR 3018126, DOI 10.1016/j.jsc.2012.05.010
D. Zywina, On the possible images of the mod $\ell$ representations associated to elliptic curves over $\mathbb {Q}$, Preprint, arXiv:1508.07660, 2015.