{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T06:53:59Z","timestamp":1776840839522,"version":"3.51.2"},"reference-count":57,"publisher":"American Mathematical Society (AMS)","issue":"357","license":[{"start":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T00:00:00Z","timestamp":1771632000000},"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                    We provide two families of algorithms to compute characteristic polynomials of endomorphisms and norms of isogenies of Drinfeld modules. Our algorithms work for Drinfeld modules of any rank, defined over any base curve. When the base curve is\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"double-struck upper P Subscript double-struck upper F Sub Subscript q Superscript 1\">\n                        <mml:semantics>\n                          <mml:msubsup>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi mathvariant=\"double-struck\">P<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:msub>\n                                  <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                    <mml:mi mathvariant=\"double-struck\">F<\/mml:mi>\n                                  <\/mml:mrow>\n                                  <mml:mi>q<\/mml:mi>\n                                <\/mml:msub>\n                              <\/mml:mrow>\n                            <\/mml:mrow>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:msubsup>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathbb P^1_{{\\mathbb {F}_q}}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , we do a thorough study of the complexity, demonstrating that our algorithms are, in many cases, the most asymptotically performant. The first family of algorithms relies on the correspondence between Drinfeld modules and Anderson motives, reducing the computation to linear algebra over a polynomial ring. The second family, available only for the Frobenius endomorphism, is based on a formula expressing the characteristic polynomial of the Frobenius as a reduced norm in a central simple algebra.\n                  <\/p>","DOI":"10.1090\/mcom\/4052","type":"journal-article","created":{"date-parts":[[2024,12,3]],"date-time":"2024-12-03T12:36:40Z","timestamp":1733229400000},"page":"415-455","source":"Crossref","is-referenced-by-count":0,"title":["Algorithms for computing norms and characteristic polynomials on general Drinfeld modules"],"prefix":"10.1090","volume":"95","author":[{"given":"Xavier","family":"Caruso","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antoine","family":"Leudi\u00e8re","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2025,2,21]]},"reference":[{"issue":"6","key":"1","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1007\/s00200-022-00588-x","article-title":"Efficient computation of Riemann-Roch spaces for plane curves with ordinary singularities","volume":"35","author":"Abelard, Simon","year":"2024","journal-title":"Appl. Algebra Engrg. Comm. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0938-1279","issn-type":"print"},{"issue":"2","key":"2","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1145\/3614408.3614417","article-title":"Drinfeld modules in SageMath","volume":"57","author":"Ayotte, David","year":"2023","journal-title":"ACM Commun. Comput. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/1932-2232","issn-type":"print"},{"issue":"2","key":"3","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1215\/S0012-7094-86-05328-7","article-title":"\ud835\udc61-motives","volume":"53","author":"Anderson, Greg W.","year":"1986","journal-title":"Duke Math. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-7094","issn-type":"print"},{"key":"4","unstructured":"[Ang94] B. Angl\u00e8s, Modules de Drinfeld sur les corps finis, Ph.D. Thesis, 1994."},{"key":"5","isbn-type":"print","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/978-3-031-15979-4_18","article-title":"On codes and learning with errors over function fields","author":"Bombar, Maxime","year":"[2022] \\copyright2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031159787"},{"issue":"2","key":"6","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1215\/S0012-7094-35-00114-4","article-title":"On certain functions connected with polynomials in a Galois field","volume":"1","author":"Carlitz, Leonard","year":"1935","journal-title":"Duke Math. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-7094","issn-type":"print"},{"key":"7","unstructured":"[Car18] P. Caranay, Computing isogeny volcanoes of rank two Drinfeld modules, Ph.D. Thesis, University of Calgary, 2018."},{"key":"8","doi-asserted-by":"crossref","unstructured":"[CG25] X. Caruso and Q. Gazda, Computation of classical and \ud835\udc63-adic \ud835\udc59-series of \ud835\udc61-motives, Res. Number Theory (2025), 11\u201335.","DOI":"10.1007\/s40993-024-00588-5"},{"key":"9","isbn-type":"print","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1090\/conm\/754\/15148","article-title":"Computing modular polynomials and isogenies of rank two Drinfeld modules over finite fields","author":"Caranay, Perlas","year":"[2020] \\copyright2020","ISBN":"https:\/\/id.crossref.org\/isbn\/9781470451639"},{"key":"10","doi-asserted-by":"publisher","first-page":"394","DOI":"10.2307\/1969013","article-title":"La th\u00e9orie du corps de classes","volume":"41","author":"Chevalley, C.","year":"1940","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"issue":"1","key":"11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ffa.2008.07.004","article-title":"Elliptic periods for finite fields","volume":"15","author":"Couveignes, Jean-Marc","year":"2009","journal-title":"Finite Fields Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/1071-5797","issn-type":"print"},{"issue":"1","key":"12","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/s11856-012-0070-8","article-title":"Fast construction of irreducible polynomials over finite fields","volume":"194","author":"Couveignes, Jean-Marc","year":"2013","journal-title":"Israel J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0021-2172","issn-type":"print"},{"key":"13","isbn-type":"print","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1145\/3087604.3087617","article-title":"Fast multiplication for skew polynomials","author":"Caruso, Xavier","year":"2017","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450350648"},{"key":"14","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1016\/j.jsc.2016.02.016","article-title":"A new faster algorithm for factoring skew polynomials over finite fields","volume":"79","author":"Caruso, Xavier","year":"2017","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"15","isbn-type":"print","volume-title":"Introduction to algorithms","author":"Cormen, Thomas H.","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9780262033848","edition":"3"},{"key":"16","unstructured":"[Con09] K. Conrad, History of class field theory, 2009, \\url{https:\/\/kconrad.math.uconn.edu\/blurbs\/gradnumthy\/cfthistory.pdf}"},{"key":"17","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/j.jsc.2020.06.007","article-title":"Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields","volume":"105","author":"Doliskani, Javad","year":"2021","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"18","first-page":"594","article-title":"Elliptic modules","volume":"94(136)","author":"Drinfel\u2032d, V. G.","year":"1974","journal-title":"Mat. Sb. (N.S.)","ISSN":"https:\/\/id.crossref.org\/issn\/0368-8666","issn-type":"print"},{"key":"19","isbn-type":"print","doi-asserted-by":"publisher","first-page":"2129","DOI":"10.1109\/FOCS57990.2023.00130","article-title":"Faster matrix multiplication via asymmetric hashing","author":"Duan, Ran","year":"[2023] \\copyright2023","ISBN":"https:\/\/id.crossref.org\/isbn\/9798350318944"},{"key":"20","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-5350-1","volume-title":"Commutative algebra","volume":"150","author":"Eisenbud, David","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/0387942688"},{"issue":"1","key":"21","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0021-8693(91)90211-P","article-title":"On finite Drinfel\u2032d modules","volume":"141","author":"Gekeler, Ernst-Ulrich","year":"1991","journal-title":"J. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0021-8693","issn-type":"print"},{"issue":"4","key":"22","doi-asserted-by":"publisher","first-page":"1695","DOI":"10.1090\/S0002-9947-07-04558-8","article-title":"Frobenius distributions of Drinfeld modules over finite fields","volume":"360","author":"Gekeler, Ernst-Ulrich","year":"2008","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"key":"23","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1145\/860854.860889","article-title":"On the complexity of polynomial matrix computations","author":"Giorgi, Pascal","year":"2003"},{"key":"24","unstructured":"[GL20] Alexandre Grishkov and Dmitry Logachev, Introduction to Anderson t-motives: a survey,  arXiv:2008.10657v3, 2020."},{"key":"25","series-title":"Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61480-4","volume-title":"Basic structures of function field arithmetic","volume":"35","author":"Goss, David","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/3540610871"},{"key":"26","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.jnt.2019.02.008","article-title":"Endomorphism rings of reductions of Drinfeld modules","volume":"212","author":"Garai, Sumita","year":"2020","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"key":"27","doi-asserted-by":"publisher","first-page":"77","DOI":"10.2307\/1996848","article-title":"Explicit class field theory for rational function fields","volume":"189","author":"Hayes, D. R.","year":"1974","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"key":"28","isbn-type":"print","first-page":"1","article-title":"A brief introduction to Drinfel\u2032d modules","author":"Hayes, David R.","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/3110131714"},{"key":"29","volume-title":"Gesammelte Abhandlungen. Erster Band. Zahlentheorie","author":"Hilbert, David","year":"1965"},{"key":"30","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02429-0","volume-title":"Finite-dimensional division algebras over fields","author":"Jacobson, Nathan","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/3540570292"},{"key":"31","unstructured":"[JN19] A. Joux and A. K. Narayanan, Drinfeld modules may not be for isogeny based cryptography, 2019, Report number: 1329."},{"issue":"11","key":"32","doi-asserted-by":"publisher","first-page":"1359","DOI":"10.1080\/00207170600726477","article-title":"Asymptotically fast polynomial matrix algorithms for multivariate systems","volume":"79","author":"Jeannerod, C.-P.","year":"2006","journal-title":"Internat. J. Control","ISSN":"https:\/\/id.crossref.org\/issn\/0020-7179","issn-type":"print"},{"key":"33","doi-asserted-by":"crossref","unstructured":"[Kal92] E. Kaltofen, On computing determinants of matrices without divisions, Proceedings of the 1992 International Symposium on Symbolic and Algebraic Computation, ISSAC\u201992.=, Association for Computing Machinery, 1992.","DOI":"10.1145\/143242.143350"},{"key":"34","first-page":"69","article-title":"\ud835\udc5d-adic properties of modular schemes and modular forms","author":"Katz, Nicholas M.","year":"1973"},{"key":"35","unstructured":"[Kro53] Leopold Kronecker, \u00dcber die algebraisch aufl\u00f6sbaren gleichungen, In K. Hensel, editor, Leopold Kronecker\u2019s Werke, Part 4, pages 4\u201311. American Mathematical Society, 1853."},{"issue":"6","key":"36","doi-asserted-by":"publisher","first-page":"1767","DOI":"10.1137\/08073408X","article-title":"Fast polynomial factorization and modular composition","volume":"40","author":"Kedlaya, Kiran S.","year":"2011","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"issue":"3-4","key":"37","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s00037-004-0185-3","article-title":"On the complexity of computing determinants","volume":"13","author":"Kaltofen, Erich","year":"2004","journal-title":"Comput. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/1016-3328","issn-type":"print"},{"key":"38","isbn-type":"print","first-page":"383","article-title":"Chtoucas de Drinfeld, formule des traces d\u2019Arthur-Selberg et correspondance de Langlands","author":"Lafforgue, Laurent","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/7040086905"},{"key":"39","series-title":"Cambridge Studies in Advanced Mathematics","isbn-type":"print","volume-title":"Cohomology of Drinfeld modular varieties. Part I","volume":"41","author":"Laumon, G\u00e9rard","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/0521470609"},{"issue":"325","key":"40","doi-asserted-by":"publisher","first-page":"2399","DOI":"10.1090\/mcom\/3517","article-title":"A fast randomized geometric algorithm for computing Riemann-Roch spaces","volume":"89","author":"Le Gluher, Aude","year":"2020","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"41","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1145\/281508.281594","article-title":"A subresultant theory for Ore polynomials with applications","author":"Li, Ziming","year":"1998"},{"key":"42","doi-asserted-by":"publisher","first-page":"Paper No. 102311, 19","DOI":"10.1016\/j.jsc.2024.102311","article-title":"Computing a group action from the class field theory of imaginary hyperelliptic function fields","volume":"125","author":"Leudi\u00e8re, Antoine","year":"2024","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"43","isbn-type":"print","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1145\/3326229.3326256","article-title":"Computing the characteristic polynomial of a finite rank two Drinfeld module","author":"Musleh, Yossef","year":"2019","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450360845"},{"key":"44","isbn-type":"print","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1145\/3597066.3597080","article-title":"Computing the characteristic polynomial of endomorphisms of a finite Drinfeld module using crystalline cohomology","author":"Musleh, Yossef","year":"[2023] \\copyright2023","ISBN":"https:\/\/id.crossref.org\/isbn\/9798400700392"},{"key":"45","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.ffa.2018.08.003","article-title":"Polynomial factorization over finite fields by computing Euler-Poincar\u00e9 characteristics of Drinfeld modules","volume":"54","author":"Narayanan, Anand Kumar","year":"2018","journal-title":"Finite Fields Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/1071-5797","issn-type":"print"},{"key":"46","doi-asserted-by":"publisher","first-page":"Paper No. 101572, 35","DOI":"10.1016\/j.jco.2021.101572","article-title":"Deterministic computation of the characteristic polynomial in the time of matrix multiplication","volume":"67","author":"Neiger, Vincent","year":"2021","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"47","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-19707-9","volume-title":"Drinfeld modules","volume":"296","author":"Papikian, Mihran","year":"[2023] \\copyright2023","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031197062"},{"key":"48","isbn-type":"print","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1090\/conm\/779\/15675","article-title":"Introduction to Drinfeld modules","author":"Poonen, Bjorn","year":"[2022] \\copyright2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9781470467944"},{"key":"49","isbn-type":"print","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1145\/1277548.1277590","article-title":"Faster algorithms for the characteristic polynomial","author":"Pernet, Cl\u00e9ment","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9781595937438"},{"key":"50","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-6046-0","volume-title":"Number theory in function fields","volume":"210","author":"Rosen, Michael","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/0387953353"},{"issue":"4","key":"51","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s00145-001-0004-9","article-title":"Public key cryptosystems based on Drinfeld modules are insecure","volume":"14","author":"Scanlon, Thomas","year":"2001","journal-title":"J. Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"key":"52","doi-asserted-by":"crossref","unstructured":"[Sil00] J. R. Silvester, Determinants of block matrices, Math. Gaz. 84 (2000), no. 501, 460\u2013467.","DOI":"10.2307\/3620776"},{"key":"53","series-title":"Springer Collected Works in Mathematics","isbn-type":"print","volume-title":"Collected papers","author":"Takagi, Teiji","year":"2014","ISBN":"https:\/\/id.crossref.org\/isbn\/9784431549949"},{"key":"54","doi-asserted-by":"crossref","unstructured":"[vdH97] J. van der Hoeven, Lazy multiplication of formal power series, Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, ISSAC\u201997, Association for Computing Machinery, 1997, pp. 17\u201320.","DOI":"10.1145\/258726.258738"},{"issue":"2","key":"55","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s00605-004-0261-4","article-title":"Weil pairing for Drinfeld modules","volume":"143","author":"van der Heiden, Gert-Jan","year":"2004","journal-title":"Monatsh. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0026-9255","issn-type":"print"},{"key":"56","series-title":"Mathematics: Theory \\& Applications","isbn-type":"print","volume-title":"Topics in the theory of algebraic function fields","author":"Villa Salvador, Gabriel Daniel","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9780817644802"},{"key":"57","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065","volume-title":"Modern computer algebra","author":"von zur Gathen, Joachim","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9781107039032","edition":"3"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2026-95-357\/S0025-5718-2025-04052-3\/S0025-5718-2025-04052-3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T05:55:21Z","timestamp":1776837321000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2026-95-357\/S0025-5718-2025-04052-3\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,21]]},"references-count":57,"journal-issue":{"issue":"357","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["S0025-5718-2025-04052-3"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/4052","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":[[2025,2,21]]}}}