Faster Modular Composition Using Relation Matrices

In this talk, we will present recent progress on computing the composition of two univariate polynomials modulo a third one: `p(a(x)) mod f(x)`. Unlike for many other problems on univariate polynomials, no quasi-linear algorithm is known for modular composition, and for a long time the fastest algebraic algorithm was that of Brent and Kung (1978). It has a complexity bound with exponent (ω+1)/2, where ω is the exponent of matrix multiplication. In the last few years, two paths towards a faster algorithm have been described, both relying on the computation of some polynomial matrix that encodes a particular basis of algebraic relations between successive powers `a(x)^k mod f(x)`. These paths can be combined, leading to a complexity exponent (ω+3)/4, under genericity assumptions on the input a(x). This talk will present the main ideas behind these improvements, and will shortly discuss software implementation aspects.
This talk is about joint work with Bruno Salvy, Éric Schost and Gilles Villard.