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 mathend000#. 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 mathend000# (in ALDOR).