- 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 .

*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

*
*

2008-03-18