Abstract
Handling polynomials is often a necessary step, either for solving theoretical problems or for modeling the physical world. In the context of dense polynomials, after many years of research, quasi-optimal algorithms have been designed for the most classical operations, such as multiplication or interpolation. However, for reasons of memory/time trade-off, it is often more appropriate to use the sparse representation of the polynomials. In this representation, optimality (or quasi-optimality) is much harder to achieve. This thesisaddresses this problem and presents new algorithms improving the known complexities for sparse polynomials.The first discussed operation is the interpolation of a sparse polynomial. Previous solutions showed a strong dependency on the underlying model and the coefficients ring. Still, no quasi-optimal algorithms exist. Our work brings a first quasi-optimal algorithm for the case of integer polynomials.In a second step, the hard question of divisibility between two sparse polynomials is addressed. First, we describe a non-trivial family of polynomials for which we propose a divisibility test in polynomial time. We also propose very efficient algorithms, optimal in some cases, to verify a product of polynomials modulo a sparse polynomial. These results lead to the first quasi-linear algorithm for the verification of sparse polynomialsproducts.Finally, the classical arithmetic operations: multiplication and division are also discussed. In particular, this thesis shows how to rely on verification and interpolation to obtain efficient algorithms. In the case of polynomials with integer coefficients, our approach reaches for the first time a quasi-optimal complexity.