{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,31]],"date-time":"2026-08-31T17:32:13Z","timestamp":1788197533678,"version":"build-2803163510"},"reference-count":25,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2015,2,1]],"date-time":"2015-02-01T00:00:00Z","timestamp":1422748800000},"content-version":"unspecified","delay-in-days":31,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["LMS J. Comput. Math."],"published-print":{"date-parts":[[2015]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the problem of efficiently constructing a curve<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline1\"\/><jats:tex-math>$C$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>of genus\u00a0<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline2\"\/><jats:tex-math>$2$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>over a finite field<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline3\"\/><jats:tex-math>$\\mathbb{F}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>for which either the curve<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline4\"\/><jats:tex-math>$C$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>itself or its Jacobian has a prescribed number<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline5\"\/><jats:tex-math>$N$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>of<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline6\"\/><jats:tex-math>$\\mathbb{F}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-rational points.<\/jats:p><jats:p>In the case of the Jacobian, we show that any \u2018CM-construction\u2019 to produce the required genus-<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline7\"\/><jats:tex-math>$2$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>curves necessarily takes time exponential in the size of its input.<\/jats:p><jats:p>On the other hand, we provide an algorithm for producing a genus-<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline8\"\/><jats:tex-math>$2$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>curve with a given number of points that, heuristically, takes polynomial time for most input values. We illustrate the practical applicability of this algorithm by constructing a genus-<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline9\"\/><jats:tex-math>$2$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>curve having exactly<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline10\"\/><jats:tex-math>$10^{2014}+9703$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>(prime) points, and two genus-<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline11\"\/><jats:tex-math>$2$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>curves each having exactly<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline12\"\/><jats:tex-math>$10^{2013}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>points.<\/jats:p><jats:p>In an appendix we provide a complete parametrization, over an arbitrary base field<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline13\"\/><jats:tex-math>$k$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>of characteristic neither two nor three, of the family of genus-<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline14\"\/><jats:tex-math>$2$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>curves over<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline15\"\/><jats:tex-math>$k$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>that have<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline16\"\/><jats:tex-math>$k$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-rational degree-<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline17\"\/><jats:tex-math>$3$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>maps to elliptic curves, including formulas for the genus-<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline18\"\/><jats:tex-math>$2$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>curves, the associated elliptic curves, and the degree-<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157014000461_inline19\"\/><jats:tex-math>$3$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>maps.<\/jats:p><jats:p><jats:uri xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:type=\"simple\" xlink:href=\"http:\/\/journals.cambridge.org\/sup_S1461157014000461sup001\">Supplementary\u00a0materials\u00a0are\u00a0available\u00a0with\u00a0this\u00a0article.<\/jats:uri><\/jats:p>","DOI":"10.1112\/s1461157014000461","type":"journal-article","created":{"date-parts":[[2015,2,4]],"date-time":"2015-02-04T09:31:46Z","timestamp":1423042306000},"page":"170-197","source":"Crossref","is-referenced-by-count":14,"title":["Genus-2 curves and Jacobians with a given number of points"],"prefix":"10.1112","volume":"18","author":[{"given":"Reinier","family":"Br\u00f6ker","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Everett W.","family":"Howe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kristin E.","family":"Lauter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Stevenhagen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2015,2,1]]},"reference":[{"key":"S1461157014000461_r5","first-page":"161","volume-title":"Arithmetics, geometry and coding theory (AGCT 2005)","volume":"21","author":"Eisentr\u00e4ger","year":"2010"},{"key":"S1461157014000461_r4","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016310902973"},{"key":"S1461157014000461_r12","first-page":"413","article-title":"Review of Legendre\u2019s Trait\u00e9 des fonctions elliptiques, troisi\u00e8me suppl\u00e9ment","volume":"8","author":"Jacobi","year":"1832","journal-title":"J. reine angew. Math."},{"key":"S1461157014000461_r2","first-page":"269","article-title":"Constructing supersingular elliptic curves","volume":"1","author":"Br\u00f6ker","year":"2009","journal-title":"J. Comb. Number Theory"},{"key":"S1461157014000461_r14","first-page":"93","article-title":"The number of curves of genus two with elliptic differentials","volume":"485","author":"Kani","year":"1997","journal-title":"J. reine angew. Math."},{"key":"S1461157014000461_r10","doi-asserted-by":"publisher","DOI":"10.1515\/form.2000.008"},{"key":"S1461157014000461_r11","doi-asserted-by":"publisher","DOI":"10.5802\/aif.2430"},{"key":"S1461157014000461_r13","volume-title":"Gesammelte Werke, B\u00e4nde I\u2013VIII","author":"Jacobi","year":"1969"},{"key":"S1461157014000461_r22","doi-asserted-by":"publisher","DOI":"10.1515\/form.2004.013"},{"key":"S1461157014000461_r20","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0441-1_21"},{"key":"S1461157014000461_r24","doi-asserted-by":"publisher","DOI":"10.1112\/S1461157012001015"},{"key":"S1461157014000461_r9","first-page":"1","article-title":"Sur un exemple de r\u00e9duction d\u2019int\u00e9grales ab\u00e9liennes aux fonctions elliptiques","volume":"1, 2nd part","author":"Hermite","year":"1876","journal-title":"Ann. Soc. Sci. Bruxelles S\u00e9r. I"},{"key":"S1461157014000461_r16","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1090\/S0002-9947-1988-0936803-3","article-title":"Curves of genus 2 with split Jacobian","volume":"307","author":"Kuhn","year":"1988","journal-title":"Trans. Amer. Math. Soc."},{"key":"S1461157014000461_r25","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0058807"},{"key":"S1461157014000461_r6","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45455-1_23"},{"key":"S1461157014000461_r3","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-07-01980-1"},{"key":"S1461157014000461_r7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0457-2_7"},{"key":"S1461157014000461_r17","volume-title":"Trait\u00e9 des fonctions elliptiques et des int\u00e9grales Eul\u00e9riennes, Tome troisi\u00e8me","author":"Legendre","year":"1828"},{"key":"S1461157014000461_r18","doi-asserted-by":"publisher","DOI":"10.4064\/aa121-3-1"},{"key":"S1461157014000461_r8","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.300"},{"key":"S1461157014000461_r23","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2013-02712-3"},{"key":"S1461157014000461_r19","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/ham021"},{"key":"S1461157014000461_r1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/83.3.532"},{"key":"S1461157014000461_r15","unstructured":"15. D. R. Kohel , \u2018Endomorphism rings of elliptic curves over finite fields\u2019, PhD\u00a0Thesis, University of California, Berkeley, 1996."},{"key":"S1461157014000461_r21","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8655-1_7"}],"container-title":["LMS Journal of Computation and Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1461157014000461","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,28]],"date-time":"2022-04-28T13:33:37Z","timestamp":1651152817000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1461157014000461\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015]]}},"alternative-id":["S1461157014000461"],"URL":"https:\/\/doi.org\/10.1112\/s1461157014000461","relation":{},"ISSN":["1461-1570"],"issn-type":[{"value":"1461-1570","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}