  A new Las Vegas algorithm is presented for the composition of two polynomials
modulo a third one, over an arbitrary field. When the degrees of these
polynomials are bounded by $n$, the algorithm uses $O(n^{1.43})$ field
operations, breaking through the $3/2$ barrier in the exponent for the first
time. The previous fastest algebraic algorithms, due to Brent and Kung in 1978,
require $O(n^{1.63})$ field operations in general, and ${n^{3/2+o(1)}}$ field
operations in the special case of power series over a field of large enough
characteristic. If cubic-time matrix multiplication is used, the new algorithm
runs in ${n^{5/3+o(1)}}$ operations, while previous ones run in $O(n^2)$
operations.
  Our approach relies on the computation of a matrix of algebraic relations
that is typically of small size. Randomization is used to reduce arbitrary
input to this favorable situation.
