The theoretical complexity of Algorithm 1
is good but does not lead to a practical implementation
of a fast multiplication of polynomials.
According to [GCL92] it is not better
than the classical algorithm for
The reasons are
We are going to get rid off these two difficulties
leading to a practical algorithm better than
the classical one for
- the recursive calls,
- the creation of intermediate polynomials.
Marc Moreno Maza