{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T04:32:46Z","timestamp":1776832366700,"version":"3.51.2"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540213246","type":"print"},{"value":"9783540246336","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24633-6_4","type":"book-chapter","created":{"date-parts":[[2010,8,2]],"date-time":"2010-08-02T08:38:22Z","timestamp":1280738302000},"page":"40-58","source":"Crossref","is-referenced-by-count":8,"title":["Linear Recurrences with Polynomial Coefficients and Computation of the Cartier-Manin Operator on Hyperelliptic Curves"],"prefix":"10.1007","author":[{"given":"Alin","family":"Bostan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierrick","family":"Gaudry","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u00c9ric","family":"Schost","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","unstructured":"Medicis, \n                  \n                    http:\/\/www.medicis.polytechnique.fr\/"},{"issue":"4","key":"4_CR2","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1137\/0204045","volume":"4","author":"A.V. Aho","year":"1975","unstructured":"Aho, A.V., Steiglitz, K., Ullman, J.D.: Evaluating polynomials at fixed sets of points. SIAM J. Comput.\u00a04(4), 533\u2013539 (1975)","journal-title":"SIAM J. Comput."},{"key":"4_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1007\/BFb0055748","volume-title":"Advances in Cryptology - CRYPTO \u201998","author":"D. Bailey","year":"1998","unstructured":"Bailey, D., Paar, C.: Optimal extension fields for fast arithmetic in public-key algorithms. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol.\u00a01462, pp. 472\u2013485. Springer, Heidelberg (1998)"},{"issue":"3","key":"4_CR4","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1016\/S0022-0000(74)80029-2","volume":"8","author":"A. Borodin","year":"1974","unstructured":"Borodin, A., Moenck, R.T.: Fast modular transforms. Comput. System Sci.\u00a08(3), 366\u2013386 (1974)","journal-title":"Comput. System Sci."},{"issue":"3-4","key":"4_CR5","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1006\/jsco.1996.0125","volume":"24","author":"W. Bosma","year":"1997","unstructured":"Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I. The user language. J. Symb. Comp.\u00a024(3-4), 235\u2013265 (1997), See also \n                  \n                    http:\/\/www.maths.usyd.edu.au:8000\/u\/magma\/","journal-title":"J. Symb. Comp."},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/860854.860870","volume-title":"Proceedings of ISSAC 2003","author":"A. Bostan","year":"2003","unstructured":"Bostan, A., Lecerf, G., Schost, \u00c9.: Tellegen\u2019s principle into practice. In: Proceedings of ISSAC 2003, pp. 37\u201344. ACM Press, New York (2003)"},{"key":"4_CR7","series-title":"Grundlehren Math. Wiss.","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03338-8","volume-title":"Algebraic complexity theory","author":"P. B\u00fcrgisser","year":"1997","unstructured":"B\u00fcrgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic complexity theory. Grundlehren Math. Wiss., vol.\u00a0315. Springer, Heidelberg (1997)"},{"issue":"7","key":"4_CR8","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/BF01178683","volume":"28","author":"D.G. Cantor","year":"1991","unstructured":"Cantor, D.G., Kaltofen, E.: On fast multiplication of polynomials over arbitrary algebras. Acta Informatica\u00a028(7), 693\u2013701 (1991)","journal-title":"Acta Informatica"},{"key":"4_CR9","first-page":"426","volume":"244","author":"P. Cartier","year":"1957","unstructured":"Cartier, P.: Une nouvelle op\u00e9ration sur les formes diff\u00e9rentielles. C. R. Acad. Sci. Paris\u00a0244, 426\u2013428 (1957)","journal-title":"C. R. Acad. Sci. Paris"},{"key":"4_CR10","first-page":"375","volume-title":"Ramanujan revisited, Urbana-Champaign, Ill, 1987","author":"D.V. Chudnovsky","year":"1988","unstructured":"Chudnovsky, D.V., Chudnovsky, G.V.: Approximations and complex multiplication according to Ramanujan. In: Ramanujan revisited, Urbana-Champaign, Ill, 1987, pp. 375\u2013472. Academic Press, Boston (1988)"},{"issue":"4","key":"4_CR11","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1145\/274888.274890","volume":"31","author":"P. Flajolet","year":"1997","unstructured":"Flajolet, P., Salvy, B.: The SIGSAM challenges: Symbolic asymptotics in practice. SIGSAM Bull.\u00a031(4), 36\u201347 (1997)","journal-title":"SIGSAM Bull."},{"key":"4_CR12","unstructured":"Gaudry, P., G\u00fcrel, N.: Counting points in medium characteristic using Kedlaya\u2019s algorithm. To appear in Experiment. Math."},{"key":"4_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/10722028_18","volume-title":"Algorithmic Number Theory","author":"P. Gaudry","year":"2000","unstructured":"Gaudry, P., Harley, R.: Counting points on hyperelliptic curves over finite fields. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol.\u00a01838, pp. 313\u2013332. Springer, Heidelberg (2000)"},{"key":"4_CR14","unstructured":"Gaudry, P., Schost, \u00c9.: Cardinality of a genus 2 hyperelliptic curve over GF(5 . 1024 + 41). e-mail to the NMBRTHRY mailing list (September 2002)"},{"key":"4_CR15","unstructured":"Hanrot, G., Quercia, M., Zimmermann, P.: The middle product algorithm, I. Speeding up the division and square root of power series (preprint)"},{"key":"4_CR16","first-page":"477","volume":"43","author":"H. Hasse","year":"1936","unstructured":"Hasse, H., Witt, E.: Zyklische unverzweigte Erweiterungsk\u00f6rper vom primzahlgrade p \u00fcber einem algebraischen Funktionenk\u00f6rper der Charakteristik p. Monatsch. Math. Phys.\u00a043, 477\u2013492 (1936)","journal-title":"Math. Phys."},{"issue":"6","key":"4_CR17","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1006\/jsco.2000.0370","volume":"29","author":"E. Kaltofen","year":"2000","unstructured":"Kaltofen, E., Corless, R.M., Jeffrey, D.J.: Challenges of symbolic computation: my favorite open problems. J. Symb. Comp.\u00a029(6), 891\u2013919 (2000)","journal-title":"J. Symb. Comp."},{"key":"4_CR18","first-page":"323","volume":"16","author":"K. Kedlaya","year":"2001","unstructured":"Kedlaya, K.: Countimg points on hyperelliptic curves using Monsky-Washnitzer. J. Ramanujan Math. Soc.\u00a016, 323\u2013338 (2001)","journal-title":"J. Ramanujan Math. Soc."},{"issue":"2-3","key":"4_CR19","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0304-3975(85)90049-0","volume":"36","author":"W. Keller-Gehrig","year":"1985","unstructured":"Keller-Gehrig, W.: Fast algorithms for the characteristic polynomial. Theor. Comput. Sci.\u00a036(2-3), 309\u2013317 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR20","first-page":"245","volume":"45","author":"J.I. Manin","year":"1965","unstructured":"Manin, J.I.: The Hasse-Witt matrix of an algebraic curve. Trans. Amer. Math. Soc.\u00a045, 245\u2013264 (1965)","journal-title":"Trans. Amer. Math. Soc."},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/3-540-45455-1_36","volume-title":"Algorithmic Number Theory","author":"K. Matsuo","year":"2002","unstructured":"Matsuo, K., Chao, J., Tsujii, S.: An improved baby step giant step algorithm for point counting of hyperelliptic curves over finite fields. In: Fieker, C., Kohel, D.R. (eds.) ANTS 2002. LNCS, vol.\u00a02369, pp. 461\u2013474. Springer, Heidelberg (2002)"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Moenck, R.T., Borodin, A.: Fast modular transforms via division. In: Thirteenth Annual IEEE Symposium on Switching and Automata Theory, Univ. Maryland, College Park, Md., pp. 90\u201396 (1972)","DOI":"10.1109\/SWAT.1972.5"},{"key":"4_CR23","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1017\/S0305004100049252","volume":"76","author":"J.M. Pollard","year":"1974","unstructured":"Pollard, J.M.: Theorems on factorization and primality testing. Proc. Cambridge Philos. Soc.\u00a076, 521\u2013528 (1974)","journal-title":"Proc. Cambridge Philos. Soc."},{"key":"4_CR24","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/BF00289470","volume":"7","author":"A. Sch\u00f6nhage","year":"1977","unstructured":"Sch\u00f6nhage, A.: Schnelle Multiplikation von Polynomen \u00fcber K\u00f6rpern der Charakteristik 2. Acta Informatica\u00a07, 395\u2013398 (1977)","journal-title":"Acta Informatica"},{"key":"4_CR25","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF02242355","volume":"7","author":"A. Sch\u00f6nhage","year":"1971","unstructured":"Sch\u00f6nhage, A., Strassen, V.: Schnelle Multiplikation gro\u00dfer Zahlen. Computing\u00a07, 281\u2013292 (1971)","journal-title":"Computing"},{"key":"4_CR26","unstructured":"Shoup, V.: NTL: A library for doing number theory, \n                  \n                    http:\/\/www.shoup.net"},{"key":"4_CR27","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/120694.120697","volume-title":"Proceedings of ISSAC 1991","author":"V. Shoup","year":"1991","unstructured":"Shoup, V.: A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic. In: Proceedings of ISSAC 1991, pp. 14\u201321. ACM Press, New York (1991)"},{"key":"4_CR28","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1515\/crll.1987.377.49","volume":"377","author":"K.-O. St\u00f6hr","year":"1987","unstructured":"St\u00f6hr, K.-O., Voloch, J.: A formula for the Cartier operator on plane algebraic curves. J. Reine Angew. Math.\u00a0377, 49\u201364 (1987)","journal-title":"J. Reine Angew. Math."},{"key":"4_CR29","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V. Strassen","year":"1969","unstructured":"Strassen, V.: Gaussian elimination is not optimal. Numer. Math.\u00a013, 354\u2013356 (1969)","journal-title":"Numer. Math."},{"key":"4_CR30","unstructured":"Strassen, V.: Einige Resultate \u00fcber Berechnungskomplexit\u00e4t. Jber. Deutsch. Math.- Verein.\u00a078(1), 1\u20138 (1976\/1977)"},{"key":"4_CR31","volume-title":"Modern computer algebra","author":"J. Gathen von zur","year":"1999","unstructured":"von zur Gathen, J., Gerhard, J.: Modern computer algebra. Cambridge University Press, Cambridge (1999)"},{"key":"4_CR32","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1090\/conm\/225\/03215","volume":"225","author":"D. Wan","year":"1999","unstructured":"Wan, D.: Computing zeta functions over finite fields. Contemp. Math.\u00a0225, 131\u2013141 (1999)","journal-title":"Contemp. Math."},{"key":"4_CR33","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1016\/0021-8693(78)90247-8","volume":"52","author":"N. Yui","year":"1978","unstructured":"Yui, N.: On the Jacobian varietes of hyperelliptic curves over fields of characteristic p > 2. J. Algebra\u00a052, 378\u2013410 (1978)","journal-title":"J. Algebra"}],"container-title":["Lecture Notes in Computer Science","Finite Fields and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24633-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,17]],"date-time":"2019-03-17T12:35:13Z","timestamp":1552826113000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24633-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540213246","9783540246336"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24633-6_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}