## Hints

Write and where are polynomials of degree less than . We want to compute . We have

with

Note that each of the polynomials has degree less than . Computing the coefficients requires
• additions in degree less than .
• multiplications in degree less than .
• additions in degree less than .
Once the coefficients have been computed the true coefficients of are not known yet. For intsance, both and contain terms in degree for . In fact, we need additions in degree less than in order to complete the job.
Let be the number of operations on the coefficients required to compute from and . We have

Using the appropiate formula from [TCS02]. we obtain

Marc Moreno Maza
2008-03-18