{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T12:45:55Z","timestamp":1760100355385,"version":"3.38.0"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,5,1]],"date-time":"2011-05-01T00:00:00Z","timestamp":1304208000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AAECC"],"published-print":{"date-parts":[[2011,5]]},"DOI":"10.1007\/s00200-011-0144-6","type":"journal-article","created":{"date-parts":[[2011,5,5]],"date-time":"2011-05-05T00:25:16Z","timestamp":1304555116000},"page":"187-217","source":"Crossref","is-referenced-by-count":10,"title":["Complexity bounds for the rational Newton-Puiseux algorithm over finite fields"],"prefix":"10.1007","volume":"22","author":[{"given":"Adrien","family":"Poteaux","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Rybowicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,5,6]]},"reference":[{"key":"144_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0265-3","volume-title":"Polynomial and Matrix Computations, Progress in Theoretical Computer Science. Vol. 1","author":"D. Bini","year":"1994","unstructured":"Bini D., Pan V.Y.: Polynomial and Matrix Computations, Progress in Theoretical Computer Science. Vol. 1. Birkh\u00e4user, Saarbr\u00fccken (1994)"},{"key":"144_CR2","doi-asserted-by":"crossref","unstructured":"Bliss, G.A.: Algebraic functions. AMS (1933)","DOI":"10.1090\/coll\/016"},{"issue":"3\u20134","key":"144_CR3","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. Comput. 24(3\u20134), 235\u2013265 (1997)","journal-title":"J. Symb. Comput."},{"key":"144_CR4","doi-asserted-by":"crossref","unstructured":"Bostan, A., Chyzak, F., Lecerf, G., Salvy, B., Schost, E.: Differential equations for algebraic functions. In: Brown, C.W. (ed.) ISSAC\u201907: Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation, pp. 25\u201332. ACM Press (2007). doi: 10.1145\/1277548.1277553","DOI":"10.1145\/1277548.1277553"},{"issue":"4","key":"144_CR5","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1145\/322092.322099","volume":"25","author":"R.P. Brent","year":"1978","unstructured":"Brent R.P., Kung H.T.: Fast algorithms for manipulating formal power series. J. ACM. 25(4), 581\u2013595 (1978). doi: 10.1145\/322092.322099","journal-title":"J. ACM."},{"key":"144_CR6","doi-asserted-by":"crossref","unstructured":"Brieskorn, E., Kn\u00f6rrer, H.: Plane Algebraic Curves. Birkha\u00fcser (1986)","DOI":"10.1007\/978-3-0348-5097-1"},{"issue":"7","key":"144_CR7","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1007\/BF01178683","volume":"28","author":"D. Cantor","year":"1990","unstructured":"Cantor D., Kaltofen E.: On fast multiplication of polynomials over arbitrary algebras. Acta Inform. 28(7), 693\u2013701 (1990)","journal-title":"Acta Inform."},{"key":"144_CR8","doi-asserted-by":"crossref","unstructured":"Chevalley, C.: Introduction to the Theory of Algebraic Functions of One Variable, Mathematical Surveys, vol. 6. AMS (1951)","DOI":"10.1090\/surv\/006"},{"key":"144_CR9","doi-asserted-by":"crossref","unstructured":"Chistov, A.L.: Polynomial complexity of the Newton-Puiseux algorithm. In: Mathematical Foundations of Computer Science 1986, pp. 247\u2013255. Springer, London, UK (1986)","DOI":"10.1007\/BFb0016248"},{"issue":"4","key":"144_CR10","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0885-064X(86)90006-3","volume":"2","author":"D.V. Chudnovsky","year":"1986","unstructured":"Chudnovsky D.V., Chudnovsky G.V.: On expansion of algebraic functions in power and Puiseux series I. J. Complex. 2(4), 271\u2013294 (1986)","journal-title":"J. Complex."},{"issue":"1","key":"144_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0885-064X(87)90002-1","volume":"3","author":"D.V. Chudnovsky","year":"1987","unstructured":"Chudnovsky D.V., Chudnovsky G.V.: On expansion of algebraic functions in power and Puiseux series II. J. Complex. 3(1), 1\u201325 (1987)","journal-title":"J. Complex."},{"key":"144_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0022-4049(84)90070-7","volume":"24","author":"P.M. Cohn","year":"1984","unstructured":"Cohn P.M.: Puiseux\u2019s theorem revisited. J. Pure Appl. Algebra 24, 1\u20134 (1984)","journal-title":"J. Pure Appl. Algebra"},{"issue":"10","key":"144_CR13","first-page":"267","volume":"2","author":"L. Comtet","year":"1964","unstructured":"Comtet L.: Calcul pratique des coefficients de Taylor d\u2019une fonction alg\u00e9brique. L\u2019Enseignement Math\u00e9matique 2(10), 267\u2013270 (1964)","journal-title":"L\u2019Enseignement Math\u00e9matique"},{"key":"144_CR14","doi-asserted-by":"crossref","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. In: STOC \u201987: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pp. 1\u20136. ACM, New York, NY, USA (1987). doi: 10.1145\/28395.28396","DOI":"10.1145\/28395.28396"},{"issue":"5","key":"144_CR15","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1006\/jsco.2002.0564","volume":"34","author":"O. Cormier","year":"2002","unstructured":"Cormier O., Singer M.F., Trager B.M., Ulmer F.: Linear differential operators for polynomial equations. J. Symbol. Comput. 34(5), 355\u2013398 (2002)","journal-title":"J. Symbol. Comput."},{"issue":"3","key":"144_CR16","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1145\/1113439.1113457","volume":"39","author":"X. Dahan","year":"2005","unstructured":"Dahan X., Schost E., Maza M.M., Wu W., Xie Y.: On the complexity of the D5 principle. SIGSAM Bull. 39(3), 97\u201398 (2005). doi: 10.1145\/1113439.1113457","journal-title":"SIGSAM Bull."},{"key":"144_CR17","doi-asserted-by":"crossref","unstructured":"Della Dora, J., Dicrescenzo, C., Duval, D.: About a new method for computing in algebraic number fields. In: EUROCAL 85. Springer-Verlag LNCS 204 (1985)","DOI":"10.1007\/3-540-15984-3_279"},{"key":"144_CR18","volume-title":"Computer Algebra in Scientific Computing, CASC 2002","author":"G. Diaz-Toca","year":"2002","unstructured":"Diaz-Toca G., Gonzalez-Vega L.: Determining Puiseux expansions by Hensel\u2019s lemma and dynamic evaluation. In: Ganzha, V., Mayr, E., Vorozhtsov, E. (eds) Computer Algebra in Scientific Computing, CASC 2002, Technische Universit\u00e4t M\u00fcnchen, Germany (2002)"},{"key":"144_CR19","unstructured":"Duval, D.: Diverses questions relatives au calcul formel avec des nombres alg\u00e9briques. Universit\u00e9 de Grenoble, Th\u00e8se d\u2019\u00c9tat (1987)"},{"issue":"2","key":"144_CR20","first-page":"119","volume":"70","author":"D. Duval","year":"1989","unstructured":"Duval D.: Rational Puiseux expansions. Compos. Math 70(2), 119\u2013154 (1989)","journal-title":"Compos. Math"},{"key":"144_CR21","volume-title":"Introduction to the Theory of Algebraic Numbers and Functions","author":"M. Eichler","year":"1966","unstructured":"Eichler M.: Introduction to the Theory of Algebraic Numbers and Functions. Academic Press, London (1966)"},{"key":"144_CR22","doi-asserted-by":"crossref","unstructured":"Henry, J.P., Merle, M.: Complexity of computation of embedded resolution of algebraic curves. In: Proceedings Eurocal 87, no. 378 in Lecture Notes in Computer Science, pp. 381\u2013390. Springer (1987)","DOI":"10.1007\/3-540-51517-8_143"},{"key":"144_CR23","doi-asserted-by":"crossref","unstructured":"Kaltofen, E.: Polynomial factorization: a success story. In: ISSAC \u201903: Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, pp. 3\u20134. ACM, New York, NY, USA (2003). doi: 10.1145\/860854.860857","DOI":"10.1145\/860854.860857"},{"key":"144_CR24","doi-asserted-by":"crossref","unstructured":"Kedlaya, K., Umans, C.: Fast modular composition in any characteristic. In: FOCS, pp. 146\u2013155. IEEE Computer Society (2008)","DOI":"10.1109\/FOCS.2008.13"},{"key":"144_CR25","doi-asserted-by":"crossref","unstructured":"Kedlaya, K.S., Umans, C.: Fast polynomial factorization and modular composition. In: STOC, pp. 481\u2013490 (2008)","DOI":"10.1145\/1374376.1374445"},{"issue":"2","key":"144_CR26","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/322063.322068","volume":"25","author":"H.T. Kung","year":"1978","unstructured":"Kung H.T., Traub J.F.: All algebraic functions can be computed fast. J. ACM 25(2), 245\u2013260 (1978)","journal-title":"J. ACM"},{"key":"144_CR27","volume-title":"Algebra","author":"S. Lang","year":"1965","unstructured":"Lang S.: Algebra. Addison-Wesley, Reading (1965)"},{"key":"144_CR28","doi-asserted-by":"crossref","unstructured":"Lecerf, G.: Fast separable factorization and applications. Appl. Algebra Eng. Commun. Comput. 19(2), (2008)","DOI":"10.1007\/s00200-008-0062-4"},{"key":"144_CR29","doi-asserted-by":"crossref","unstructured":"Li, X., Maza, M.M., Schost, E.: Fast arithmetic for triangular sets: from theory to practice. In: ISSAC \u201907: Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation, pp. 269\u2013276. ACM, New York, NY, USA (2007) doi: 10.1145\/1277548.1277585","DOI":"10.1145\/1277548.1277585"},{"key":"144_CR30","volume-title":"Maple 10 Programming Guide","author":"M.B. Monagan","year":"2005","unstructured":"Monagan M.B., Geddes K.O., Heal K.M., Labahn G., Vorkoetter S.M., McCarron J., DeMarco P.: Maple 10 Programming Guide. Maplesoft, Waterloo (2005)"},{"key":"144_CR31","doi-asserted-by":"crossref","unstructured":"Poteaux, A.: Computing monodromy groups defined by plane algebraic curves. In: Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation, pp. 36\u201345. ACM, New-York (2007)","DOI":"10.1145\/1277500.1277509"},{"key":"144_CR32","unstructured":"Poteaux, A.: Calcul de d\u00e9veloppements de Puiseux et application au calcul de groupe de monodromie d\u2019une courbe alg\u00e9brique Plane. Ph.D. thesis, Universit\u00e9 de Limoges (2008)"},{"key":"144_CR33","doi-asserted-by":"crossref","unstructured":"Poteaux, A., Rybowicz, M.: Good reduction of Puiseux series and complexity of the Newton-Puiseux algorithm. In: ISSAC \u201908: Proceedings of the 2008 International Symposium on Symbolic and Algebraic Computation, pp. 239\u2013246. ACM, New-York (2008)","DOI":"10.1145\/1390768.1390802"},{"key":"144_CR34","unstructured":"Poteaux, A., Rybowicz, M.: Towards a Symbolic-Numeric Method to Compute Puiseux Series: The Modular Part. http:\/\/arxiv.org\/abs\/0803.3027 (2008)"},{"key":"144_CR35","doi-asserted-by":"crossref","unstructured":"Poteaux, A., Rybowicz, M.: Good reduction of Puiseux series and applications. J. Symbol. Comput. (To appear, 2011)","DOI":"10.1016\/j.jsc.2011.08.008"},{"key":"144_CR36","unstructured":"Poteaux, A., Schost, E.: Modular composition modulo triangular sets and applications. Comput. Complex. (Submitted, 2010)"},{"key":"144_CR37","doi-asserted-by":"crossref","unstructured":"Reischert, D.: Asymptotically fast computations of subresultants. In: ISSAC \u201997: Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, pp. 233\u2013240. ACM, ACM Press (1997)","DOI":"10.1145\/258726.258792"},{"key":"144_CR38","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1145\/373500.373502","volume":"1","author":"T. Sasaki","year":"2000","unstructured":"Sasaki T., Inaba D.: Hensel construction of $${f(x,u_1,\\dots,u_l)}$$ at a singular point and its application. Sigsam Bull. 1, 9\u201317 (2000)","journal-title":"Sigsam Bull."},{"key":"144_CR39","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02242355","volume":"7","author":"A. Sch\u00f6nage","year":"1971","unstructured":"Sch\u00f6nage A., Strassen V.: Schnelle multiplikation gro\u00dfer zahlen. Comput. 7, 281\u2013292 (1971)","journal-title":"Comput."},{"key":"144_CR40","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1006\/jsco.1994.1025","volume":"17","author":"V. Shoup","year":"1993","unstructured":"Shoup V.: Fast construction of irreducible polynomials over finite fields. J. Symbol. Comput. 17, 371\u2013391 (1993)","journal-title":"J. Symbol. Comput."},{"key":"144_CR41","doi-asserted-by":"crossref","unstructured":"Shoup, V.: Efficient computation of minimal polynomials in algebraic extensions of finite fields. In: ISSAC \u201999: Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, pp. 53\u201358. ACM, New York, NY, USA (1999) doi: 10.1145\/309831.309859","DOI":"10.1145\/309831.309859"},{"issue":"190","key":"144_CR42","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1090\/S0025-5718-1990-1010602-1","volume":"54","author":"J. Teitelbaum","year":"1990","unstructured":"Teitelbaum J.: The computational complexity of the resolution of plane curve singularities. Math. Comp. 54(190), 797\u2013837 (1990)","journal-title":"Math. Comp."},{"issue":"1","key":"144_CR43","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/S0304-3975(98)00102-9","volume":"210","author":"J. Hoeven van der","year":"1999","unstructured":"van der Hoeven J.: Fast evaluation of holonomic functions. Theor. Comput. Sci. 210(1), 199\u2013215 (1999)","journal-title":"Theor. Comput. Sci."},{"issue":"3\u20134","key":"144_CR44","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1016\/j.jsc.2004.11.012","volume":"39","author":"J. Hoeven van der","year":"2005","unstructured":"van der Hoeven J.: Effective analytic functions. J. Symbol. Comput. 39(3\u20134), 433\u2013449 (2005)","journal-title":"J. Symbol. Comput."},{"key":"144_CR45","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1006\/jsco.1994.1051","volume":"18","author":"M. Hoeij van","year":"1994","unstructured":"van Hoeij M.: An algorithm for computing an integral basis in an algebraic function field. J. Symbol. Comput. 18, 353\u2013363 (1994)","journal-title":"J. Symbol. Comput."},{"key":"144_CR46","volume-title":"Modern Computer Algebra","author":"J. zur Gathen von","year":"1999","unstructured":"von zur Gathen J., Gerhard J.: Modern Computer Algebra. Cambridge University Press, Cambridge (1999)"},{"issue":"1\u20132","key":"144_CR47","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1006\/jsco.1999.1002","volume":"31","author":"J. Von Zur Gathen","year":"2001","unstructured":"Von Zur Gathen J., Panario D.: Factoring polynomials over finite fields: a survey. J. Symbo. Comput. 31(1\u20132), 3\u201317 (2001). doi: 10.1006\/jsco.1999.1002","journal-title":"J. Symbo. Comput."},{"key":"144_CR48","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-6323-4","volume-title":"Algebraic Curves","author":"R.J. Walker","year":"1978","unstructured":"Walker R.J.: Algebraic Curves. Springer, Berlin (1978)"},{"key":"144_CR49","doi-asserted-by":"crossref","first-page":"369","DOI":"10.2140\/pjm.1999.188.369","volume":"188","author":"P.G. Walsh","year":"1999","unstructured":"Walsh P.G.: On the complexity of rational Puiseux expansions. Pac. J. Math. 188, 369\u2013387 (1999)","journal-title":"Pac. J. Math."},{"key":"144_CR50","doi-asserted-by":"crossref","first-page":"1167","DOI":"10.1090\/S0025-5718-00-01246-1","volume":"69","author":"P.G. Walsh","year":"2000","unstructured":"Walsh P.G.: A polynomial-time complexity bound for the computation of the singular part of an algebraic function. Math. Comput. 69, 1167\u20131182 (2000)","journal-title":"Math. Comput."},{"key":"144_CR51","doi-asserted-by":"crossref","unstructured":"Yun, D.D.Y.: On square-free decomposition algorithms. In: Proceedings SYMSAC \u201976. ACM (1976)","DOI":"10.1145\/800205.806320"},{"key":"144_CR52","volume-title":"Le probl\u00e8me des modules pour les branches planes","author":"O. Zariski","year":"1981","unstructured":"Zariski O.: Le probl\u00e8me des modules pour les branches planes. Hermann, Paris (1981)"}],"container-title":["Applicable Algebra in Engineering, Communication and Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-011-0144-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00200-011-0144-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-011-0144-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,5]],"date-time":"2025-03-05T11:15:01Z","timestamp":1741173301000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00200-011-0144-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,5]]}},"alternative-id":["144"],"URL":"https:\/\/doi.org\/10.1007\/s00200-011-0144-6","relation":{},"ISSN":["0938-1279","1432-0622"],"issn-type":[{"type":"print","value":"0938-1279"},{"type":"electronic","value":"1432-0622"}],"subject":[],"published":{"date-parts":[[2011,5]]}}}