{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T05:05:38Z","timestamp":1776834338418,"version":"3.51.2"},"reference-count":44,"publisher":"American Mathematical Society (AMS)","issue":"335","license":[{"start":{"date-parts":[[2022,11,23]],"date-time":"2022-11-23T00:00:00Z","timestamp":1669161600000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    In this work, we establish a link between the classification of ECM-friendly elliptic curves and Mazur\u2019s program B, which consists in parameterizing all the families of elliptic curves with exceptional Galois image. Motivated by Barbulescu et al. [ANTS X\u2013proceedings 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\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"j\">\n                        <mml:semantics>\n                          <mml:mi>j<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">j<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    -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\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"a equals negative 1\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>a<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mo>\n                              \u2212\n                              \n                            <\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">a=-1<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    twisted Edwards\u2019 form are new.\n                  <\/p>","DOI":"10.1090\/mcom\/3697","type":"journal-article","created":{"date-parts":[[2021,9,15]],"date-time":"2021-09-15T09:57:38Z","timestamp":1631699858000},"page":"1405-1436","source":"Crossref","is-referenced-by-count":1,"title":["A classification of ECM-friendly families of elliptic curves using modular curves"],"prefix":"10.1090","volume":"91","author":[{"given":"Razvan","family":"Barbulescu","sequence":"first","affiliation":[]},{"given":"Sudarshan","family":"Shinde","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2021,11,23]]},"reference":[{"issue":"201","key":"1","doi-asserted-by":"publisher","first-page":"399","DOI":"10.2307\/2153176","article-title":"Finding suitable curves for the elliptic curve method of factorization","volume":"60","author":"Atkin, A. O. L.","year":"1993","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"2","article-title":"Crible alg\u00e9brique: Distribution, optimisation \u2014 number field sieve (cado-nfs)","author":"Bai, Shi"},{"key":"3","unstructured":"[BGGM14] R. Barbulescu, P. Gaudry, A. Guillevic, and F. Morain, Discrete logarithms in GF(\ud835\udc5d\u00b2) \u2014 160 digits, 2014, Announcement available at the NMBRTHRY archives, Item 004706"},{"key":"4","isbn-type":"print","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-662-46800-5_6","article-title":"Improving NFS for the discrete logarithm problem in non-prime finite fields","author":"Barbulescu, Razvan","year":"2015","ISBN":"https:\/\/id.crossref.org\/isbn\/9783662468005"},{"key":"5","isbn-type":"print","doi-asserted-by":"publisher","first-page":"63","DOI":"10.2140\/obs.2013.1.63","article-title":"Finding ECM-friendly curves through a study of Galois properties","author":"Barbulescu, Razvan","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9781935107019"},{"issue":"303","key":"6","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1090\/mcom\/3112","article-title":"Some mathematical remarks on the polynomial selection in NFS","volume":"86","author":"Barbulescu, Razvan","year":"2017","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"7","unstructured":"[BS19] R. Barbulescu and S. Shinde, Online complement for \u201cA classification of ECM-friendly families using modular curves\u201d, 2019, \\url{https:\/\/razvanbarbulescu.pages.math.cnrs.fr\/ECMfriendly\/ECMfriendly.html}."},{"issue":"282","key":"8","doi-asserted-by":"publisher","first-page":"1139","DOI":"10.1090\/S0025-5718-2012-02633-0","article-title":"ECM using Edwards curves","volume":"82","author":"Bernstein, Daniel J.","year":"2013","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"9","isbn-type":"print","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/978-3-540-68164-9_26","article-title":"Twisted Edwards curves","author":"Bernstein, Daniel J.","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540681595"},{"key":"10","first-page":"61","article-title":"Starfish on strike","author":"Bernstein, D. J.","year":"2010"},{"key":"11","isbn-type":"print","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/978-3-319-22174-8_15","article-title":"Twisted Hessian curves","author":"Bernstein, Daniel J.","year":"2015","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319221748"},{"key":"12","isbn-type":"print","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/978-3-030-45388-6_17","article-title":"Faster cofactorization with ECM using mixed representations","author":"Bouvier, Cyril","year":"[2020] \\copyright2020","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030453886"},{"key":"13","isbn-type":"print","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-642-14518-6_11","article-title":"New families of ECM curves for Cunningham numbers","author":"Brier, \u00c9ric","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642145179"},{"key":"14","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1515\/crll.1984.351.66","article-title":"Genera of congruence subgroups in \ud835\udc44-quaternion algebras","volume":"351","author":"Cox, David A.","year":"1984","journal-title":"J. Reine Angew. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0075-4102","issn-type":"print"},{"issue":"1-2","key":"15","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1006\/jsco.1998.1004","article-title":"Classical invariants and 2-descent on elliptic curves","volume":"31","author":"Cremona, J. E.","year":"2001","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"1","key":"16","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1142\/S1793042107000833","article-title":"Smooth numbers in short intervals","volume":"3","author":"Croot, Ernie","year":"2007","journal-title":"Int. J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/1793-0421","issn-type":"print"},{"issue":"2","key":"17","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1080\/10586458.2003.10504495","article-title":"Congruence subgroups of \ud835\udc43\ud835\udc46\ud835\udc3f(2,\u2124) of genus less than or equal to 24","volume":"12","author":"Cummins, C. J.","year":"2003","journal-title":"Experiment. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1058-6458","issn-type":"print"},{"key":"18","first-page":"1","article-title":"Serre\u2019s constant of elliptic curves over the rationals","author":"Daniels, Harris B.","year":"2019","journal-title":"Exp.\\ Math."},{"key":"19","unstructured":"[DRM21] H. B. Daniels, \u00c1. Lozano-Robledo, and J. S. Morrow, Towards a classification of entanglements of Galois representations attached to elliptic curves, Preprint,  arXiv:2105.02060, 2021."},{"key":"20","unstructured":"[DM20] H. B. Daniels and J. S. Morrow, A group theoretic perspective on entanglements of division fields, Preprint,  arXiv:2008.09886, 2020."},{"key":"21","isbn-type":"print","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1145\/3087604.3087606","article-title":"Parametrizations for families of ECM-friendly curves","author":"G\u00e9lin, Alexandre","year":"2017","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450350648"},{"key":"22","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1112\/S1461157016000231","article-title":"JKL-ECM: an implementation of ECM using Hessian curves","volume":"19","author":"Heer, Henriette","year":"2016","journal-title":"LMS J. Comput. Math."},{"key":"23","unstructured":"[JM20] N. Jones and K. McMurdy, Elliptic curves with non-abelian entanglements, Preprint,  arXiv:2008.09087, 2020."},{"issue":"242","key":"24","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1090\/S0025-5718-02-01482-5","article-title":"Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the Gaussian integer method","volume":"72","author":"Joux, Antoine","year":"2003","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"25","isbn-type":"print","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1007\/978-3-662-53018-4_20","article-title":"Extended tower number field sieve: a new complexity for the medium prime case","author":"Kim, Taechan","year":"2016","ISBN":"https:\/\/id.crossref.org\/isbn\/9783662530184"},{"issue":"2","key":"26","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1112\/plms\/s3-33.2.193","article-title":"Universal bounds on the torsion of elliptic curves","volume":"33","author":"Kubert, Daniel Sion","year":"1976","journal-title":"Proc. London Math. Soc. (3)","ISSN":"https:\/\/id.crossref.org\/issn\/0024-6115","issn-type":"print"},{"key":"27","isbn-type":"print","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/BFb0091537","article-title":"The number field sieve","author":"Lenstra, A. K.","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540570136"},{"issue":"3","key":"28","doi-asserted-by":"publisher","first-page":"649","DOI":"10.2307\/1971363","article-title":"Factoring integers with elliptic curves","volume":"126","author":"Lenstra, H. W., Jr.","year":"1987","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"issue":"177","key":"29","doi-asserted-by":"publisher","first-page":"243","DOI":"10.2307\/2007888","article-title":"Speeding the Pollard and elliptic curve methods of factorization","volume":"48","author":"Montgomery, Peter L.","year":"1987","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"30","volume-title":"An FFT extension of the elliptic curve method of factorization","author":"Montgomery, Peter Lawrence","year":"1992"},{"key":"31","volume-title":"Polynomial selection for the number field sieve integer factorisation algorithm","author":"Murphy, Brian Antony","year":"1999"},{"key":"32","isbn-type":"print","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/BFb0091538","article-title":"The lattice sieve","author":"Pollard, J. M.","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540570136"},{"key":"33","doi-asserted-by":"publisher","first-page":"Paper No. 12, 34","DOI":"10.1007\/s40993-015-0013-7","article-title":"Elliptic curves over \u211a and 2-adic images of Galois","volume":"1","author":"Rouse, Jeremy","year":"2015","journal-title":"Res. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/2522-0160","issn-type":"print"},{"issue":"4","key":"34","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01405086","article-title":"Propri\u00e9t\u00e9s galoisiennes des points d\u2019ordre fini des courbes elliptiques","volume":"15","author":"Serre, Jean-Pierre","year":"1972","journal-title":"Invent. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0020-9910","issn-type":"print"},{"key":"35","series-title":"Lecture Notes in Mathematics, Vol. 627","isbn-type":"print","volume-title":"Modular functions of one variable. VI","year":"1977","ISBN":"https:\/\/id.crossref.org\/isbn\/3540085300"},{"key":"36","series-title":"Kan\\^{o} Memorial Lectures, No. 1","volume-title":"Introduction to the arithmetic theory of automorphic functions","author":"Shimura, Goro","year":"1971"},{"key":"37","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-09494-6","volume-title":"The arithmetic of elliptic curves","volume":"106","author":"Silverman, Joseph H.","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387094939","edition":"2"},{"key":"38","doi-asserted-by":"publisher","first-page":"Paper No. e4, 79","DOI":"10.1017\/fms.2015.33","article-title":"Computing images of Galois representations attached to elliptic curves","volume":"4","author":"Sutherland, Andrew V.","year":"2016","journal-title":"Forum Math. Sigma"},{"issue":"5","key":"39","doi-asserted-by":"publisher","first-page":"1199","DOI":"10.2140\/ant.2017.11.1199","article-title":"Modular curves of prime-power level with infinitely many rational points","volume":"11","author":"Sutherland, Andrew V.","year":"2017","journal-title":"Algebra Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/1937-0652","issn-type":"print"},{"key":"40","article-title":"Informal preliminary report (8)","author":"Suyama, Hiromi","year":"1985"},{"key":"41","first-page":"90","article-title":"An algorithm for computing the Weierstrass normal form","author":"van Hoeij, Mark","year":"1995"},{"issue":"2-3","key":"42","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1006\/jsco.1996.0084","article-title":"Rational parametrizations of algebraic curves using a canonical divisor","volume":"23","author":"van Hoeij, Mark","year":"1997","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"43","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.jsc.2012.05.010","article-title":"Generating subfields","volume":"52","author":"van Hoeij, Mark","year":"2013","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"44","unstructured":"[Zyw15] D. Zywina, On the possible images of the mod \u2113 representations associated to elliptic curves over \u211a, Preprint,  arXiv:1508.07660, 2015."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2022-91-335\/S0025-5718-2021-03697-2\/S0025-5718-2021-03697-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T04:29:32Z","timestamp":1776832172000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2022-91-335\/S0025-5718-2021-03697-2\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,23]]},"references-count":44,"journal-issue":{"issue":"335","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["S0025-5718-2021-03697-2"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3697","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2021,11,23]]}}}