Modular Composition for Decomposable Polynomials

Modular composition is one of the operations on polynomials in A[ x ] (A a commutative ring) for which no quasi-linear algorithm is known. Given polynomials f, g, a in A[ x ], with f monic of degree n and g, a of degrees less than n , it amounts to computing g ( a ) rem f , where rem denotes the Euclidean division remainder. When A is the finite field F q , this operation is a major ingredient for fast factorization algorithms in F q [ x ] [5, 9, 10]. Another important particular case is with f = x n , that is, composition of power series, which itself is an important ingredient in algorithms such as power series reversion, or the solution of certain functional equations [3].