Improving Complexity Bounds for the Computation of Puiseux Series over Finite Fields

International audienceLet L be a field of characteristic p with q elements and F ∈ L[X, Y ] be a polynomial with p > deg Y (F) and total degree d. In [40], we showed that rational Puiseux series of F above X = 0 could be computed with an expected number of O˜d 3 log q) arithmetic operations in L. In this paper, we reduce this bound to O˜og q) using Hensel lifting and changes of variables in the Newton-Puiseux algorithm that give a better control of the number of steps. The only asymptotically fast algorithm required is polynomial multiplication over finite fields. This approach also allows to test the irreducibility of F in L[[X]][Y ] with Oõperations in L. Finally, we describe a method based on structured bivariate multiplication [34] that may speed up computations for some input