, )) operations in K . Once done, every element in the basis can be represented by a vector of polynomials in K [x] whose degrees are bounded by E. To put the above integral basis in triangular form, it suffices to compute a Hermite Normal Form of a full rank n × n polynomial matrix. Using [17, Theorem 1.2] an algorithm by Labahn, Neiger and Zhou performs this task in O(n ??1 M (?)) operations in K . We can finally apply Proposition 11 and deduce the minimal local contribution for the factor ? in O, the denominators is bounded a priori by E := E(f ) + max 1?i?r c i so we can truncate all series beyond this exponent. Indeed, forgetting the higher order terms amounts to subtracting each

V. Arvind and . Vijayaraghavan, The complexity of solving linear equations over a finite ring, Annual Symposium on Theoretical Aspects of Computer Science, pp.472-484, 2005.

J. Bauch, Computation of integral bases, Journal of Number Theory, vol.165, pp.382-407, 2016.

J. Böhm, W. Decker, S. Laplagne, and G. Pfister, Computing integral bases via localization and Hensel lifting, 2015.

J. Böhm, W. Decker, S. Laplagne, and G. Pfister, Andreas Steenpaß, and Stefan Steidel. Parallel algorithms for normalization, Journal of Symbolic Computation, vol.51, pp.99-114, 2013.

A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf et al., Algorithmes efficaces en calcul formel, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01431717

B. Niel-de, On the complexity of solving linear congruences and computing nullspaces modulo a constant, 2012.

T. and G. Pfister, Local analytic geometry: Basic theory and applications, 2013.

J. Della-dora, C. Dicrescenzo, and D. Duval, About a new method for computing in algebraic number fields, European Conference on Computer Algebra, pp.289-290, 1985.

C. Diem, On arithmetic and the discrete logarithm problem in class groups of curves. Habilitation, 2009.

D. Duval, Rational Puiseux expansions, Compositio mathematica, vol.70, issue.2, pp.119-154, 1989.

F. Hess, Computing Riemann-Roch spaces in algebraic function fields and related topics, Journal of Symbolic Computation, vol.33, issue.4, pp.425-445, 2002.

. Mark-van-hoeij, An algorithm for computing an integral basis in an algebraic function field, Journal of Symbolic Computation, vol.18, issue.4, pp.353-363, 1994.

A. Mark-van-hoeij and . Novocin, A reduction algorithm for algebraic function fields, 2008.

M. Mark-van-hoeij and . Stillman, Computing an integral basis for an algebraic function field, 2015.

G. Joris-van-der-hoeven and . Lecerf, Directed evaluation. working paper or preprint, 2018.

S. Kiran, C. Kedlaya, and . Umans, Fast polynomial factorization and modular composition, SIAM Journal on Computing, vol.40, issue.6, pp.1767-1802, 2011.

G. Labahn, V. Neiger, and W. Zhou, Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix, Journal of Complexity, vol.42, pp.44-71, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01345627

F. Gall, Powers of tensors and fast matrix multiplication, Proceedings of the 39th international symposium on symbolic and algebraic computation, pp.296-303, 2014.

G. Moroz and É. Schost, A fast algorithm for computing the truncated resultant, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, pp.341-348, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01366386

V. Neiger, Fast computation of shifted Popov forms of polynomial matrices via systems of modular polynomial equations, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, pp.365-372, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01266014

A. Poteaux and M. Weimann, Computing Puiseux series: a fast divide and conquer algorithm, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01578214

. Barry-marshall-trager, Algorithms for manipulating algebraic functions, 1976.

. Barry-marshall-trager, Integration of algebraic functions, 1984.

J. Robert and . Walker, Algebraic curves, 1950.

H. Zassenhaus, Ein algorithmus zur berechnung einer minimalbasis über gegebener ordnung, Funktionalanalysis Approximationstheorie Numerische Mathematik, pp.90-103, 1967.