This talk is about algorithms for modular composition of polynomials, and for the related problems of inverse modular composition and modular power projection. For two univariate polynomials a and g over a commutative field, modular composition asks to compute b = h(a) mod g for some given h; inverse modular composition asks to compute h such that h(a) = b mod g for some given b; and modular power projection asks to compute the list of projections ell(1), ell(a mod g), ..., ell(a^{n-1} mod g) for some given linear functional ell over the polynomials modulo g, with n the degree of g. For generic g and a, we propose algorithms whose complexity bound improves upon previous algorithms, which come from Brent and Kung's 1978 approach; the new complexity bound is subquadratic in the degree of g and a even when using cubic-time matrix multiplication. Our improvement comes from the fast computation of specific bases of bivariate ideals and operations with these bases thanks to fast univariate polynomial matrix algorithms.
Contains joint work with Seung Gyu Hyun, Bruno Salvy, Eric Schost, Gilles Villard.
