Efficient implementation

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 $n \leq 300$ . The reasons are

• the recursive calls,
• the creation of intermediate polynomials.

We are going to get rid off these two difficulties leading to a practical algorithm better than the classical one for $n \geq 32$ (in ALDOR).