{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:26Z","timestamp":1750694726728},"reference-count":18,"publisher":"Wiley","issue":"A","license":[{"start":{"date-parts":[[2016,8,26]],"date-time":"2016-08-26T00:00:00Z","timestamp":1472169600000},"content-version":"unspecified","delay-in-days":238,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["LMS J. Comput. Math."],"published-print":{"date-parts":[[2016]]},"abstract":"<jats:p>In this paper, we present novel algorithms for finding small relations and ideal factorizations in the ideal class group of an order in an imaginary quadratic field, where both the norms of the prime ideals and the size of the coefficients involved are bounded. We show how our methods can be used to improve the computation of large-degree isogenies and endomorphism rings of elliptic curves defined over finite fields. For these problems, we obtain improved heuristic complexity results in almost all cases and significantly improved performance in practice. The speed-up is especially high in situations where the ideal class group can be computed in advance.<\/jats:p>","DOI":"10.1112\/s1461157016000358","type":"journal-article","created":{"date-parts":[[2016,8,26]],"date-time":"2016-08-26T15:30:30Z","timestamp":1472225430000},"page":"371-390","source":"Crossref","is-referenced-by-count":7,"title":["Fast heuristic algorithms for computing relations in the class group of a quadratic order, with applications to isogeny evaluation"],"prefix":"10.1112","volume":"19","author":[{"given":"Jean-Fran\u00e7ois","family":"Biasse","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Claus","family":"Fieker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"suffix":"Jr","given":"Michael J.","family":"Jacobson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2016,8,26]]},"reference":[{"key":"S1461157016000358_r13","doi-asserted-by":"publisher","DOI":"10.1112\/S1461157014000151"},{"key":"S1461157016000358_r12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2005.04.013"},{"key":"S1461157016000358_r8","unstructured":"8. R. Dupont , \u2018Moyenne arithm\u00e9tico-g\u00e9om\u00e9trique, suites de Borchardt et applications\u2019, PhD Thesis, \u00c9cole Polytechnique, 2006."},{"key":"S1461157016000358_r4","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1007\/978-3-540-85538-5_7","volume-title":"Pairing-based Cryptography \u2013 Pairing 2008, Proceedings of Second International Conference, Egham, September 1\u20133, 2008","author":"Br\u00f6ker","year":"2008"},{"key":"S1461157016000358_r5","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2011-02508-1"},{"key":"S1461157016000358_r3","doi-asserted-by":"publisher","DOI":"10.1016\/j.jnt.2009.11.003"},{"key":"S1461157016000358_r6","first-page":"1","article-title":"Constructing elliptic curve isogenies in quantum subexponential time","volume":"8","author":"Childs","year":"2013","journal-title":"J.\u00a0Math. Cryptol."},{"key":"S1461157016000358_r1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380857"},{"key":"S1461157016000358_r15","first-page":"307","volume-title":"International Symposium on Symbolic and Algebraic Computation, ISSAC\u201913, Boston, MA, June 26\u201329, 2013","author":"Pauderis","year":"2013"},{"key":"S1461157016000358_r14","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100295"},{"key":"S1461157016000358_r10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jnt.2008.11.006"},{"key":"S1461157016000358_r16","doi-asserted-by":"publisher","DOI":"10.5802\/jtnb.142"},{"key":"S1461157016000358_r18","first-page":"531","volume-title":"Proceedings of the Tenth Algorithmic Number Theory Symposium (ANTS X)","author":"Sutherland","year":"2013"},{"key":"S1461157016000358_r2","doi-asserted-by":"publisher","DOI":"10.1515\/jmc.2011.008"},{"key":"S1461157016000358_r7","volume-title":"A course in computational algebraic number theory","author":"Cohen","year":"1991"},{"key":"S1461157016000358_r9","first-page":"839","article-title":"A rigorous subexponential algorithm for computation of class groups","volume":"2","author":"Hafner","year":"1989","journal-title":"J.\u00a0Amer. Math. Soc."},{"key":"S1461157016000358_r17","unstructured":"17. N. Stephens-Davidowitz , \u2018Dimension-preserving reductions between lattice problems\u2019, http:\/\/www.noahsd.com\/latticeproblems.pdf."},{"key":"S1461157016000358_r11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14518-6_19"}],"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\/S1461157016000358","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,13]],"date-time":"2019-09-13T00:27:50Z","timestamp":1568334470000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1461157016000358\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"references-count":18,"journal-issue":{"issue":"A","published-print":{"date-parts":[[2016]]}},"alternative-id":["S1461157016000358"],"URL":"https:\/\/doi.org\/10.1112\/s1461157016000358","relation":{},"ISSN":["1461-1570"],"issn-type":[{"value":"1461-1570","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}